归并排序的两种实现

归并排序(MERGE-SORT)简单来说就是将大的序列先视为若干个比较小的数组,分成几个比较小的结构,然后是利用归并的思想实现的排序方法,该算法采用经典的分治策略(分就是将问题分(divide)成一些小的问题分别求解,而治(conquer)则将分的阶段得到的各答案"合"在一起)。

image-20240304125652060

很明显,递归的结束条件是当只剩一个数时

  • 这里的mid是为了将区间分开,如{8,5,7}会按左边开始分:{8,5}和{7}
  • merge的作用就是将两段区间进行排序,如{8},{4}两个无需拆分,只需要进行换位即可,方便期间可以使用一个额外的数组,将两段区间排好序的数放在新数组

如:{1,3}{2,6},a指针指向左边区间,b指针指向右区间,依次指向排好序的各自区间,然后每一次两个数组的数组进行比较,按照顺序放入辅助数组

递归

代码如下:

public static void mergeSort1(int[] nums) {
     sort(nums,0,nums.length-1);
 }
public static void sort(int[] nums, int left, int right) {
        // 剩余一个数时停止
        if (left == right)
            return;
        int mid = (left + right) >> 1;
        sort(nums, left, mid);
        sort(nums,mid + 1, right);
        merge(nums, left, right, mid);
    }

    public static void merge(int[] arr, int start, int end, int mid) {
        int a = start;
        int b = mid + 1;
        int i = start;
        while (a <= mid && b <= end) {
            helper[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        // 处理最终的边界值,只会执行其中一个并且一次
        while (a <= mid) {
            //这里最后一个值是在mid左边
            helper[i++] = arr[a++];
        }
        while (b <= end) {
              //这里最后一个值是在mid右边
            helper[i++] = arr[b++];
        }
        //避免重新定义变量,使用i
        for ( i = start; i <= end; i++) {
            arr[i] = helper[i];
        }
    }

merge代码解析:

当第一个while循环结束时,此时已经将区间重新拍好,但是最后会剩余一个数,因此再对最后一个数进行处理

最后,可以看一下递归的顺序图

image-20240304132114755

迭代

merge的代码可以进行复用,迭代代码讲解:

  • 首先迭代与递归不同之处在于:迭代是由小区间逐渐增大,而递归是大区间逐渐细化,也就是方向不同
  • 迭代使用步长,初始为1,每次增加一倍,不超过数组的长度
  • if (mid + 1 >= n)判断是为了当步长划分时,到达数组最后一位停止

但是 right = Math.min(left + ( step<<1) - 1, n - 1);这里是为了,选择一个更小值,因为假如n=10步长为4时,此时右边区间第一位则是2*step+left-1而不是数组最后一位.

  • 最后的left = right + 1;则是每一小区间结束后+1,对下一个小区间进行merge
  public static void mergeSort2(int[] nums) {
        int n = nums.length;
        for (int left, mid, right, step = 1; step < n; step <<= 1) {
            left = 0;
            while (left < n) {
                mid = left + step - 1;
                if (mid + 1 >= n) {
                    break;
                }
                // 有可能剩余的不止最后一个,因此要选择最小值
                right = Math.min(left + ( step<<1) - 1, n - 1);
                merge(nums, left, right, mid);
                // 下一组
                left = right + 1;

            }
        }
    }
 public static void merge(int[] arr, int start, int end, int mid) {
        int a = start;
        int b = mid + 1;
        int i = start;
        while (a <= mid && b <= end) {
            helper[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        // 处理最终的边界值
        while (a <= mid) {
            helper[i++] = arr[a++];
        }
        while (b <= end) {
            helper[i++] = arr[b++];
        }
        for ( i = start; i <= end; i++) {
            arr[i] = helper[i];
        }
    }