归并排序

arr先保证局部有序,再慢慢变得整体有序

实际并没有分割数组

 public static void mergeSort(int[] arr, int left, int right, int mid) {
		// 归并排序的过程是先分组,然后两两合并,最终变得有序

 		// 左指针不小于右指针时,递归结束
        if (left >= right) {
            return;
        }
        // 先分组左半部分,本质是将指针指向
        mergeSort(arr, left, mid, (left + mid) / 2);
        // 再分组右半部分
        mergeSort(arr, mid + 1, right, (mid + 1 + right) / 2);
        // 分好组之后,合并排序
        sort(arr, left, right, mid);
    }


    public static void sort(int[] arr, int left, int right, int mid) {
		// 临时数组保存排序数据
        int[] temp = new int[right - left + 1];
        int s1 = left;
        int s2 = mid + 1;
        // 比较两个序列之间的最小数谁最小,放入temp中
        int i = 0;
        while (s1 <= mid && s2 <= right) {
            if (arr[s1] < arr[s2]) {
                temp[i] = arr[s1];
                i++;
                s1++;
            } else {
                temp[i] = arr[s2];
                i++;
                s2++;
            }

        }
        // 将剩余数字放入temp中
        while (s1 <= mid) {
            temp[i] = arr[s1];
            i++;
            s1++;
        }
        while (s2 <= right) {
            temp[i] = arr[s2];
            i++;
            s2++;
        }
		// 数据从临时数组取出,覆盖原数组
        for (int j = 0; j < temp.length; j++) {
        	// 注意是left + j,因为temp是小数组
            arr[left + j] = temp[j];
        }
    }
上一篇:oracle杀外部连接会话


下一篇:mysql 常见数据处理 dml