归并排序

归并排序

步骤

1. 先选择分界点
2. 先递归排序
3. 归并 合二为一

Support/typora-user-images/image-20210419120203122.png

private static void mergeSort(int[] array, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        mergeSort(array, l, mid);
        mergeSort(array, mid+1, r);
        // 整合
        int[] tmp = new int[r - l + 1]; // 临时数组, 用于临时存储 [l,r]区间内排好序的数据
        int i = l, j = mid + 1, k = 0;  // 两个指针
        // 进行归并
        while (i <= mid && j <= r) {
            if (array[i] <= array[j]) 
                tmp[k++] = array[i++];
            else
                tmp[k++] = array[j++];
        }

        while (i <= mid) tmp[k++] = array[i++];
        while (j <= r) tmp[k++] = array[j++];

        // 进行赋值
        for (i = l, j = 0; i <= r; i++, j++)
            array[i] = tmp[j];
    }