java 排序算法之归并排序

目录

• 简单介绍
• 基本思想
• 思路分析
• 代码实现

• 对代码的一些改进

 /**
     * 
     *  最难的是合并,所以可以先完成合并的方法，此方法请参考 基本思想 和 思路分析中的图解来完成
     *  动脑筋
     *
     * 
     *
     * @param arr   要排序的原始数组
     * @param left  因为是合并，所以要得到左右两边的的数组信息，这个是左侧数组的第一个索引值
     * @param mid   因为是一个数组，标识是第一个数组的最后一个索引，即 mid+1 是右侧数组的第一个索引，即中间索引
     * @param right 右侧数组的结束索引，右边数组的最后一个数
     * @param temp  临时空间，临时数组
     */
    public void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // 定时临时变量，用来遍历数组比较
        int l = left;  // 左边有序数组的初始索引
        int r = mid + 1; // 右边有序数组的初始索引
        int t = 0; // temp 数组中当前最后一个有效数据的索引
        // 1. 按思路先将两个数组（有序的）有序的合并到 temp 中
        // 因为是合并两个数组，所以需要两边的数组都还有值的时候才能进行 比较合并
        // 若其中一个数组的值遍历完了（取完了），那么就跳出该循环，把另一个数组所剩的值，直接copy进临时数组即可
        while (l <= mid && r <= right) {
            // 如果左边的比右边的小，则将左边的该元素填充到 temp 中
            // 并移动 t++,l++,好继续下一个
            if (arr[l] < arr[r]) {
                temp[t] = arr[l];
                t++;//移动 temp 临时数组中当前最后一个有效数据的索引
                l++; //左边原始数组的索引移动
            }
            // 否则则将右边的移动到 temp 中
            else {
                temp[t] = arr[r];
                t++;//移动 temp 临时数组中当前最后一个有效数据的索引
                r++;//右边原始数组的索引移动
            }
        }
        // 2. 如果有任意一边的数组还有值，则依序将剩余数据填充到 temp 中
        // 如果左侧还有值
        while (l <= mid) {
            temp[t] = arr[l];
            t++;
            l++;
        }
        // 如果右侧还有值
        while (r <= right) {
            temp[t] = arr[r];
            t++;
            r++;
        }
        // 3. 将 temp 数组，拷贝到原始数组
        // 注意：只拷贝当前temp有效数据到对应的原始数据中，通俗点说，就是原始数组中要排序的数据，通过temp排成了有序的，然后将temp中的有序数据将原始数组中原来要排序的那部分覆盖了就行了
        int tempL = left; // 从左边开始拷贝，左边第一个值的索引
        t = 0;  // temp 中的有效值索引，有效值边界可以通过 right 判定，因为合并两个数组到 temp 中，边界就是 right ，这里自己好好想想
        /*
         * 对于 8,4,5,7,1,3,6,2 这个数组,
         * 从栈顶开始合并：8,4 | 5,7       1,3 | 6,2
         * 先左递归的话：
         * 第一次：8,4 合并：tempL=0，right=1
         * 第二次：5,7 合并：tempL=2，right=3
         * 第三次：4,8 | 5，7 进行合并，tempL=0，right=3
         * 直到左递归完成，得到左侧一个有序的序列：4,5,7,8 然后再开始递归右边那个无序的
         * 最后回到栈底分解成两个数组的地方，将两个数组合并成一个有序数组
         * 这里真的得自己想了，我只能这么说了。
         */
        System.out.println("tempL=" + tempL + "; right=" + right);
        while (tempL <= right) {
            arr[tempL] = temp[t];
            tempL++;
            t++;
        }
    }

    @Test
    public void sortTest() {
        int[] arr = new int[]{8, 4, 5, 7, 1, 3, 6, 2};
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println("排序后：" + Arrays.toString(arr));
    }
    /**
     * 分 和 合并
     */
    public void mergeSort(int[] arr, int left, int right, int[] temp) {
        //确保两个数组中分别都存在至少一个数字
        if (left < right) {
            int mid = (left + right) / 2;
            // 先分解左侧
            mergeSort(arr, left, mid, temp);
            // 再分解右侧
            mergeSort(arr, mid + 1, right, temp);
            // 最后合并
            // 由于是递归，合并这里一定是栈顶的先执行(两边数组各只有一个数时)
            // 第一次：left = 0,right=1
            // 第二次：left = 2,right=3
            // 第三次：left = 0，right=3
//            System.out.println("left=" + left + "；right=" + right);
            merge(arr, left, mid, right, temp);
        }
    }
     /**
     * 
     *  最难的是合并,所以可以先完成合并的方法，此方法请参考 基本思想 和 思路分析中的图解来完成
     *  动脑筋
     *
     * 
     *
     * @param arr   要排序的原始数组
     * @param left  因为是合并，所以要得到左右两边的的数组信息，这个是左侧数组的第一个索引值
     * @param mid   因为是一个数组，标识是第一个数组的最后一个索引，即 mid+1 是右侧数组的第一个索引，即中间索引
     * @param right 右侧数组的结束索引，右边数组的最后一个数
     * @param temp  临时空间，临时数组
     */
    public void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // 定时临时变量，用来遍历数组比较
        int l = left;  // 左边有序数组的初始索引
        int r = mid + 1; // 右边有序数组的初始索引
        int t = 0; // temp 数组中当前最后一个有效数据的索引
        // 1. 按思路先将两个数组（有序的）有序的合并到 temp 中
        // 因为是合并两个数组，所以需要两边的数组都还有值的时候才能进行 比较合并
        // 若其中一个数组的值遍历完了（取完了），那么就跳出该循环，把另一个数组所剩的值，直接copy进临时数组即可
        while (l <= mid && r <= right) {
            // 如果左边的比右边的小，则将左边的该元素填充到 temp 中
            // 并移动 t++,l++,好继续下一个
            if (arr[l] < arr[r]) {
                temp[t] = arr[l];
                t++;//移动 temp 临时数组中当前最后一个有效数据的索引
                l++; //左边原始数组的索引移动
            }
            // 否则则将右边的移动到 temp 中
            else {
                temp[t] = arr[r];
                t++;//移动 temp 临时数组中当前最后一个有效数据的索引
                r++;//右边原始数组的索引移动
            }
        }
        // 2. 如果有任意一边的数组还有值，则依序将剩余数据填充到 temp 中
        // 如果左侧还有值
        while (l <= mid) {
            temp[t] = arr[l];
            t++;
            l++;
        }
        // 如果右侧还有值
        while (r <= right) {
            temp[t] = arr[r];
            t++;
            r++;
        }
        // 3. 将 temp 数组，拷贝到原始数组
        // 注意：只拷贝当前temp有效数据到对应的原始数据中，通俗点说，就是原始数组中要排序的数据，通过temp排成了有序的，然后将temp中的有序数据将原始数组中原来要排序的那部分覆盖了就行了
        int tempL = left; // 从左边开始拷贝，左边第一个值的索引
        t = 0;  // temp 中的有效值索引，有效值边界可以通过 right 判定，因为合并两个数组到 temp 中，边界就是 right ，这里自己好好想想
        /*
         * 对于 8,4,5,7,1,3,6,2 这个数组,
         * 从栈顶开始合并：8,4 | 5,7       1,3 | 6,2
         * 先左递归的话：
         * 第一次：8,4 合并：tempL=0，right=1
         * 第二次：5,7 合并：tempL=2，right=3
         * 第三次：4,8 | 5，7 进行合并，tempL=0，right=3
         * 直到左递归完成，得到左侧一个有序的序列：4,5,7,8 然后再开始递归右边那个无序的
         * 最后回到栈底分解成两个数组的地方，将两个数组合并成一个有序数组
         * 这里真的得自己想了，我只能这么说了。
         */
        System.out.println("tempL=" + tempL + "; right=" + right);
        while (tempL <= right) {
            arr[tempL] = temp[t];
            tempL++;
            t++;
        }
    }

public class MyMergeSortTest {
    @Test
    public void sortTest() {
        int[] arr = new int[]{8, 4, 5, 7, 1, 3, 6, 2};
        mergeSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }
    public void mergeSort(int arr[]) {
        int[] temp = new int[arr.length];
        doMergeSort(arr, 0, arr.length - 1, temp);
    }
    /**
     * 分治 与 合并
     *
     * @param arr
     * @param left
     * @param right
     * @param temp
     */
    private void doMergeSort(int[] arr, int left, int right, int[] temp) {
        // 当还可以分解时，就做分解操作
        if (left < right) {
            int mid = (left + right) / 2;
            // 先左递归分解
            doMergeSort(arr, left, mid, temp);
            // 再右递归分解
            doMergeSort(arr, mid + 1, right, temp);
            // 左递归分解到栈顶时，其实也是分为左右数组
            // 左右都到栈顶时，开始合并：
            // 第一次：合并的是 0,1 的索引,分解到最后的时候，其实只有一个数为一组，所以第一次合并是合并两个数字
            merge(arr, left, mid, right, temp);
        }
    }
    /**
     * 开始合并，每次合并都是两组，第一次合并是两个数字，左右一组都只有一个数字
     *
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @param temp
     */
    private void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // 1. 按照规则，将 temp 数组填充
        // 2. 当任意一边填充完成后，剩余未填充的依次填充到 temp 数组中
        // 3. 将 temp 数组的有效内容，拷贝会原数组，也就是将这次排序好的数组覆盖回原来排序的原数组中
        int l = left; // 左侧数组初始索引
        int r = mid + 1; // 右侧数组初始索引
        int t = 0; // 当前 temp 中有效数据的最后一个元素索引
        // 1. 按照规则，将 temp 数组填充
        // 当两边都还有数字可比较的时候，进行比较，然后填充 temp 数组
        // 只要任意一边没有数值可用时，就仅需到下一步骤
        while (l <= mid && r <= right) {
            // 当左边比右边小时，则填充到 temp 数组中
            if (arr[l] < arr[r]) {
                // 赋值完成后，t 和 l 都需要 +1，往后移动一个位置
                // t++ 是先把 t 进行赋值，再进行 t+1 操作
                temp[t++] = arr[l++];
            } else {
                // 当不满足时，则说明 右侧数字比左侧的小，进行右侧的填充
                temp[t++] = arr[r++];
            }
        }
        // 2. 有可能有其中一边会有剩余数字未填充到 temp 中，进行收尾处理
        while (l <= mid) {
            temp[t++] = arr[l++];
        }
        while (r <= right) {
            temp[t++] = arr[r++];
        }
        // 3. 将这个有序数组，覆盖会原始排序的数组中
        t = 0;
        int tempL = left; // 从左侧开始，到右侧结束，就是这一次要合并的两组数据
        while (tempL <= right) {
            arr[tempL++] = temp[t++];
        }
    }
}

    /**
     * 大量数据排序时间测试
     */
    @Test
    public void bulkDataSort() {
        int max = 80000;
//        max = 8;
        int[] arr = new int[max];
        for (int i = 0; i < max; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        if (arr.length < 10) {
            System.out.println("原始数组：" + Arrays.toString(arr));
        }
        Instant startTime = Instant.now();
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        if (arr.length < 10) {
            System.out.println("排序后：" + Arrays.toString(arr));
        }
        Instant endTime = Instant.now();
        System.out.println("共耗时：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
    }