合并排序 | 晨星的博客

一个比较经典的的排序算法

合并排序的由来

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。发明者约翰·冯·诺伊曼[1]

基本原理

将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾[1]

代码实现

递归版本

最重要的就是合并（merge）过程

我们需要两边数组的范围进行合并排序
代码如下

//l左起点 r右边界 mid左边界
public static void merge(int[] arr, int l, int r, int mid) {

        int length = r - l + 1;
        int[] arrHelp = new int[length];//存放排序的数组
        int index = 0; //拷贝计数
        int right = mid + 1; //右指针
        int left = l; //左指针

        while (left <= mid && right <= r) {
            arrHelp[index++] = 
                //哪边数组小 拷贝 指针加一
                arr[left] < arr[right] ? arr[left++] : arr[right++];
        }
        while (left <= mid) {
            //右数组空了 左数组剩下的全部拷贝
            arrHelp[index++] = arr[left++];
        }
        while (right <= r) {
             //左数组空了 同理
            arrHelp[index++] = arr[right++];
        }

        for (int i = l; i <= r; i++) {
            arr[i] = arrHelp[i - l]; //拷贝到原数组
        }

    }

递归调用

  public static void mergeSort(int[] arr, int l, int r) {
      if (arr.length == 0) return;
      if (l == r) return; //basecase
      
//防止数据越界的求中值的写法
  	//等于 （l + r）/2
      int mid = l + ((r - l) >> 1);
      //排序左边
      mergeSort(arr, l, mid);
      //排序右边
      mergeSort(arr, mid + 1, r);
      //左右合并
      merge(arr, l, r, mid);
  }

非递归版本（优化空间复杂度）

当然递归的版本空间复杂度不好所以进行优化

//非递归
public static void mergeSort(int[] arr) {
    //if (arr.length == 0) return;
    
    int mergeSize = 1;//开始范围大小
    
    while (mergeSize < arr.length) {
        
        int L = 0;//初始位置
        while (L < arr.length) {
            int mid = L + mergeSize - 1;//左边界
            if (mid >= arr.length) break;
            int R = Math.min(mid + mergeSize, arr.length - 1);//右边界
            merge(arr, L, R, mid);//合并排序
            L = R + 1;//下一个mergeSize
        }
        //防止下面的翻倍溢出
        if (mergeSize > arr.length / 2) break;
        
        mergeSize <<= 1;//Size翻倍
    }


}

总结

时间复杂度的函数为

$O(N*log(N))$

空间复杂度即需要一个相同大小的临时数组

$O(N)$

拷贝的时候可以保证相等是先拷贝左再拷贝右所以是稳定的排序算法

每日一句

凭君莫话封候事，一将功成万骨枯 ————曹松《己亥岁二首》

参考

百度百科