余睿的博客

浮生若梦,别多会少,不如莫遇

0%

归并排序

原理

归并排序(MergeSort)采用了分治的思想(Divide And Conquer)

总的来说,整个排序思想可分为如下几部分:

  1. 将待排序序列一分为二O(1)
  2. 子序列递归排序O(log n)
  3. 合并有序子序列O(n)

真个排序过程如下如所示:

归并排序示意图

分治(Divide And Conquer)

由上述的基本原理,我们可以写出该算法的基本框架:

1
2
3
4
5
6
7
void mergeSort(int* a, int lo, int hi) {
if (hi - lo < 2)return;//递归基,不可再分
int mi = (lo + hi) >> 1;//中点位置
mergeSort(a, lo, mi);//对前半部分排序
mergeSort(a, mi, hi);//对后半部分排序
merge(a, lo, mi, hi);//归并
}

该函数的实现很简单,可对应于上面的三部分:

  1. 将该序列长度除以二得到中点,并以中点为界。
  2. 分别深入前半段以及后半段进行分治。
  3. 通过merge将两个序列合并。

当只有一个元素,即不可再分的时候终止递归。观察上面的框架可以发现,其主要要实现的是如何合并两个已经有序的序列?

归并(merge)

在归并时,会使用一个数组来保存有序的结果,每次对左(a[lo,mi))右(a[mi,hi))两个子序列的前两个元素进行比较,然后将更小者加入到数组中。依次内推,从而将两个序列合并为一个有序的序列。如下图所示:

归并示意图

在上面的归并过程中,对于每一次操作,取出两个序列的第一个数字进行比较(如步骤a23),然后将更小者(如步骤b)加入数组中,依此类推,最后得到一个有序的序列。

稍加观察我们不难发现,我们如果我们用一个数组来存储a[lo,mi)的值,那么我们就可以直接在原数组上进行操作。具体如下图所示:

归并排序示意

如上图所示,a为待排序的数组,我么用left数组来存储a[lo,mi)范围内的数据,然后让一个right指针指向mi的位置,从而将a[lo..mi..hi)变为left[lo,mi)以及right[mi,hi)两个序列。

然后循环整个a数组,每一次循环将两个序列首的更小者加入a中,进而合并为一整个有序序列,最后将left的空间释放掉即可。

1
2
3
4
5
6
7
8
9
10
11
12
void merge(int *a, int lo, int mi, int hi) {
int n1 = mi - lo;//前半段长度
int* left = new int[n1];
for (int i = 0; i < n1; i++)left[i] = a[lo + i];//复制a[lo,mi)到left
int* right = a + mi;//后半段从a+mi开始

//i<n1即前半段已经全部到位,此时后半段必然有序,无需继续进行
for (int i = 0, j = 0, k = lo; i < n1;)
//j>=hi-mi即后半段复制已经完成,此时只需依次复制前半段即可
a[k++] = (j >= hi-mi || left[i] <= right[j]) ? left[i++] : right[j++];
delete[]left;//释放临时的数组
}

正确性

初始化:在循环第一次迭代前,有k=lo,此时a[lo,k)为空;又因为i=j=0,所以left[i]以及right[j]都是各自所在元素中未被复制的最小元素。

保持:

  1. left[i] <= right[j]的时候,left[i]是二者中的更小值,所以a[k]的值更新为left[i]的值,并且i以及k加一;
  2. 反之,当left[i] >= right[j]时,所以a[k]的值更新为right[j]的值,并且j以及k加一。
  3. 对于以上这两种情况,已有序的区间都由原来的a[lo,k)变为a[lo,k+1)
  4. 还有一种特殊情况对应于j>=hi-mi,此时,右半段right[mi,hi)的元素以及全部复制到a[lo,k)中,仅剩下left[i,mi)的元素未就位,由于left中的元素已经有序,所以只需要将left[i,mi)的元素依次复制到a[k,hi)中即可,而无需去比较left[i] <= right[j],这也就是||短路运算符的作用。

终止:i<n1时,循环终止,这是left[lo,mi)的元素已经全部复制到a[lo,k)中,循环终止。如果right[j,hi)中任有元素,由于right数组本省就有序,并且right就是指向a数组的,所以其必然有序。循环终止。

复杂度

对于分治的的过程,其时间复杂度为O(log n),归并的时间复杂度为O(n),所以整体时间复杂度为O(nlogn)

空间复杂度来源于归并过程中的辅组数组,由于只存储了a[lo,mi)的内容,所以空间复杂度为O(n/2)

欢迎关注我的其它发布渠道