排序-归并排序

归并排序

定义

归并排序（merge sort）是高效的基于比较的稳定排序算法

性质

归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为 \(O(nlogn)\)，空间复杂度为 \(O(n)\)。

归并排序可以只使用 \(O(1)\) 的辅助空间，但为便捷通常使用与原数组等长的辅助数组。

过程

合并

归并排序最核心的部分是 合并（merge）过程：将两个有序的数组 \(a[i]\) 和 \(b[i]\) 合并为一个有序数组 \(c[k]\)。

从左往右枚举 \(a[i]\) 和 \(b[j]\)，找出最小的值并放入数组 \(c[k]\)；重复上述过程直到 \(a[i]\) 和 \(b[j]\) 有一个为空时，将另一个数组剩下的元素放入 \(c[k]\) 。

为保证排序的稳定性，前段首元素小于或等于后端首元素时（\(a[i]\leq b[j]\)）而非小于时（\(a<b\)），就要作为最小值放入 \(c[k]\)

数组实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge(const int *a, int aLen, const int *b, int bLen, int *c) {
  int i = 0, j = 0, k = 0;
  while (i < aLen && j < bLen) {
    if (b[j] < a[i]) {  // <!> 先判断 b[j] < a[i]，保证稳定性
      c[k] = b[j];
      ++j;
    } else {
      c[k] = a[i];
      ++i;
    }
    ++k;
  }
  // 此时一个数组已空，另一个数组非空，将非空的数组并入 c 中
  for (; i < aLen; ++i, ++k) c[k] = a[i];
  for (; j < bLen; ++j, ++k) c[k] = b[j];
}

分治法实现归并排序

  1. 当数组长度为 \(1\) 时，该数组就已经是有序的，不用再分解。
  2. 当数组长度大于 \(1\) 时，该数组很可能是不是有序的。此时将该数组分为两段，再分别检查两个数组是否有序。如果有序，则将它们合并为一个有序数组；否则对不有序的数组重复第 \(2\) 条，再合并。
1
2
3
4
5
6
7
8
9
10
void merge_sort(int *a,int l,int r){
    if(r - l <= 1) return;
    int mid = l+((r-l)>>1);
    merge_sort(a,l,mid);
    merge_sort(a,mid,r);
    int tmp[10010] = {}; //结合实际情况设置tmp长度（与a相同）
    merge(a+l,mid-l,a+mid,r-mid,tmp+l);
    for(int i=l;i<r;i++) a[i] = tmp[i];
}

倍增法实现归并排序

已知当数组长度为 \(1\) 时，该数组就是已经有序的。

将数组全部切成长度为 \(1\) 的段。

从左往右依次合并两个长度为 \(1\) 的有序段，得到一系列长度 \(\leq2\) 的有序段；

从左往右依次合并两个长度为 \(\leq 2\) 的有序段，得到一系列长度 \(\leq 4\) 的有序段；

从左往右依次合并两个长度为 \(\leq 4\) 的有序段，得到一系列长度 \(\leq8\) 的有序段；

……

重复上述过程，直至数组只剩一个有序段，该段就是排序好的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
void merge_sort(int *a,int n){
    int tmp[1024]={}; //结合情况设置大小
    
    for(int seg = 1; seg<n; seg<<=1){
        for(int l1 = 0;l1 < n-seg;l1 += 2*seg){
            int r1 = l1 + seg;
            int l2 = r1;
            int r2 = min(l2+seg,n);
            merge(a+l1,a+r1,a+l2,a+r2,tmp+l1);
            for(int i=l1;i<r2;i++) a[i] = tmp[i];
        }
    }
}