数据结构第八章（四）-归并排序和基数排序

归并排序和基数排序

一、归并排序

归并（Merge）也是人如其名，把两个或多个已经有序的序列合并成一个。英文更加直观，其实就是序列融合在一起

1.归并

我们就先来用一个栗子说明“把两个或多个已经有序的序列合并成一个”这个过程。

首先肯定少不了“两个有序序列”，除了这个还需要一个能放下这两个有序序列的所有元素的顺序表，如下所示：

可以看到我们分别用指针 i ，指针 j 来指向两个顺序表，用指针 k 指向我们需要放入的顺序表。

我们对比 指针 i ，指针 j 所指元素，选择更小的一个放入 指针 k 所指的位置

打比方说，如果此时 指针 i 指向的元素更小，那么把指针 i 所指元素放进去，然后指针 i 再向后挪一格，再次对比……直到其中一个遍历完：

此时指针 j 所指顺序表已经遍历完成，则指针 i 不用再接着往下遍历了，直接把指针 i 所在顺序表中的剩余元素加入到合并的顺序表中

即 只剩一个子表未合并时，可以将该表中剩余元素全部加到总表，如下所示：

归并是把两个或多个已有序列合并成一个，那么把几个有序序列合并，就成为几路归并；

以上就是二路归并，简单吧。

当然，显然我们 “2路” 归并，每选出一个小元素则需对比关键字 1 次。

我们来看看 “4路” 归并：

显然，我们 “4路” 归并是：对比 p1、p2、p3、p4 所指元素，选择更小的一个放入 k 所指位置

当然，我们 “4路” 归并，每选出一个小元素则需对比关键字 3 次。

所以 m路归并，每选出一个元素需要对比关键字 m-1 次。

2.算法过程

还是用栗子来描述，我们的初始序列如下：

这是乱序的。

现在我们要对它进行一趟“2路”归并，也就是两个两个进行归并

我们每一“路”都只有1个元素：

此刻我们再对它进行一趟“2路”归并，也就是两个两个进行归并

我们每一“路”都有2个或1个元素：

此刻我们再对它进行一趟“2路”归并，也就是两个两个进行归并

我们每一“路”都有4个或3个元素：

我们的归并排序就完成了。

我们来整体看一下更直观：

可以看出，我们的核心操作其实就是把数组内的两个有序序列归并为一个，那么由此可得，我们代码的主要函数就是实现这个操作。

话不多说，上代码：

int *B = (int *)malloc(n*sizeof(int)); //辅助数组B

//A[low……mid]和A[mid+1……high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    
    for(k = low; k <= high; k++){
        B[k] = A[k];        //将A中所有元素复制到B中
    }
    
    for(i = low,j = mid+1,k = i; i<=mid&&j<=high; k++){
        if(B[i] <= B[j]){
            A[k] = B[i++];  //将较小值复制到A中
        }else{
            A[k] = B[j++];
        }
    }
    
    while(j<=mid){
        A[k++] = B[i++];
    }
    
    while(j<=high){
        A[k++] = B[j++];
    }
}

可以看出，我们是先将 A数组 中 [low，high] 内的元素复制到辅助数组B 中，再把 A数组 当成是最终放置数组，对 数组B 里面的 [low……mid]和[mid+1……high] 进行归并

而且我们可以注意到，当两个元素相等的时候，我们优先使用靠前的那个，这样可以保证我们的稳定性。

最后两个 while 是说，当我们遍历完其中一个的时候，另一个就不用遍历了，直接 没有归并完的部分复制到 A数组 的尾部 就可以了。

那么讲完了把两个有序序列合并为一个的过程，现在可以讲我们的归并排序了。3 2 1~上代码：

int *B = (int *)malloc(n*sizeof(int)); //辅助数组B

//A[low……mid]和A[mid+1……high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    
    for(k = low; k <= high; k++){
        B[k] = A[k];        //将A中所有元素复制到B中
    }
    
    for(i = low,j = mid+1,k = i; i<=mid&&j<=high; k++){
        if(B[i] <= B[j]){
            A[k] = B[i++];  //将较小值复制到A中
        }else{
            A[k] = B[j++];
        }
    }
    
    while(j<=mid){
        A[k++] = B[i++];
    }
    
    while(j<=high){
        A[k++] = B[j++];
    }
}



void MergeSort(int A[],int low,int high){
    
    if(low<high){
        int mid = (low+high)/2; //从中间划分
        
        MergeSort(A,low,mid);   //对左半部分归并排序（递归）
        
        MergeSort(A,mid+1,high);//对右半部分归并排序（递归）
        
        Merge(A,low,mid,high);  //归并
    }
}

看到了吗，其实我们的归并排序使用递归实现的。

抽象来看，我们递归出口的上一层就是 low和high相邻着，此时 mid 就和low一样了，再调用 MergeSort 的时候，就可以跳出往下执行了，往下发现mid+1 和 high一样，再跳出往下，就可以执行 Merge 了。

注意，Merge 和 MergeSort 不一样哈。

执行我们的 Merge ，把这两个元素排序归并排序（每个子序列都只含有1个元素），就可以执行下一个递归的两个元素了……以此类推，每两个元素都递归进行归并排序后，就可以再往上进行了，把我们之前归并好的继续合并就可以了。

如果用递归树来，就可以更好地展示我们的递归过程，就是个样子：

初始调用: [8,3,5,1,7,2]
├─ 左递归 [8,3,5]
│ ├─ 左递归 [8,3]
│ │ ├─ 左递归 [8] (终止)
│ │ ├─ 右递归 [3] (终止)
│ │ └─ 合并 → [3,8]
│ ├─ 右递归 [5] (终止)
│ └─ 合并 → [3,5,8]
├─ 右递归 [1,7,2]
│ ├─ 左递归 [1,7]
│ │ ├─ 左递归 [1] (终止)
│ │ ├─ 右递归 [7] (终止)
│ │ └─ 合并 → [1,7]
│ ├─ 右递归 [2] (终止)
│ └─ 合并 → [1,2,7]
└─ 合并 → [1,2,3,5,7,8]

很清晰直观吧。

3.性能

空间复杂度也是显然，我们搞了一个辅助数组B，所以我们空间复杂度是 O(n).

还记得我们“2路”归并排序的整体观看吗？就是这个：

有没有发现，其实这个很像是一棵倒过来的树！！！

所以其实 “2路” 归并的“归并树”，形态上就是一棵倒立的 二叉 树

那我们又知道，二叉树的第 h 层最多有 2^h-1 个结点是吧

所以 若树高为 h ，则应该满足 n ≤ 2^h-1（我们 n 是我们的初始序列个数哈，不是总结点）

由 n ≤ 2^h-1 得，h-1 = ⌈log₂n⌉

所以 n 个元素进行 2 路归并排序，归并趟数 = ⌈log₂n⌉

又因为每趟归并时间复杂度为 O(n)，则算法时间复杂度为 O( nlog₂n )

为啥每趟归并时间复杂度都是 O(n) 呢？因为每对比关键字1次，就能挑出最小的值放到归并位置上，所以我们每一趟的对比，最多对比 n-1 次，不会再多了。

归并排序是稳定的，因为当两个元素相等的时候，我们优先使用靠前的那个，所以靠前的还是靠前。

二、基数排序

基数排序（Radix Sort），这玩意儿有点意思，和我们之前说的所有的排序算法都不一样，且听我细细道来

1.算法过程

下面用一个栗子来说基数排序的过程，这是我们的初始序列，要求是得到按关键字“递减”的有序序列：

我们把每一个元素按照 “个位”、“十位”、“百位” 的方式，一趟一趟进行分配排序。

第 1 趟：以“个位”进行“分配”

先准备10个队列，分别表示个位 0~9 ：

我们从前往后把 个位数 是几分别放到对应的队列中串起来，前面是队头，后面是队尾（注意，该队列进入的时候是从队尾进入，出的时候是从队头出）：

我们再 按照“个位”递减 排序，把串起来的再从上往下捋出来，就是这样：

那么第 1 趟就分配结束了。

可以看到得到的序列中的 个位 是递减的。

第 2 趟：以“十位”进行“分配”

还是准备10个队列，分别表示十位 0~9 ：

我们从前往后把 十位数 是几分别放到对应的队列中串起来，前面是队头，后面是队尾：

（弱弱说一句哈， 可以看到我们每一个串串上面，都是“个位数”高的在上面，“个位数”低的在下面，即“个位”越大的越先入队。这样我们在捋的时候就可以保证同样的十位，个位大的在前面，个位小的在后面了~）

我们再 按照“十位”递减 排序，把串起来的再从上往下捋出来，就是这样：

那么第 2 趟就分配结束了。

可以看到得到的序列中的 十位 是递减的， 十位 相同的按 个位 递减排序。

第 3 趟：以“百位”进行“分配”

最后仍然是准备10个队列，分别表示 百位 0~9 ：

我们从前往后把 百位数 是几分别放到对应的队列中串起来，前面是队头，后面是队尾：

（我再多说一句哈， 可以看到我们每一个串串上面，都是“十位数”高的在上面，“十位数”低的在下面，即“十位”越大的越先入队；“十位数”相同的话，“个位数”高的在上面，“个位数”低的在下面。这样我们在捋的时候就可以保证同样的十位，个位大的在前面，个位小的在后面了，同样的百位，十位大的在前面，十位小的在后面了）

我们再 按照“百位”递减 排序，把串起来的再从上往下捋出来，就是这样：

那么第 2 趟就分配结束了。

可以看到得到的序列中的 百位 是递减的， 百位 相同的按 十位 递减排序， 十位 相同的按 个位 递减排序。

没想到吧，这就讲完了，这就是基数排序。

我们来整体看一下，更加直观：

2.定义

我们其实现在已经知道了基数排序是怎么个意思了，所以我们看定义就能一下看明白了：

假设长度为 n 的线性表中每个结点 a_j 的关键字由 d 元组（k^d-1，k^d-2，k^d-3，……，k¹，k⁰）组成
其中，0 ≤ kⁱ ≤ r-1（0 ≤ j ≤ n，0 ≤ i ≤ d-1），r 就是我们所说的 “基数”。

这很好理解吧，我们刚刚的元素是三位数，即上面说的“ d 元组”，d 是3，k^d-1 是最高位关键字（最主位关键字），k⁰ 是最低位关键字（最次位关键字）

就是刚刚的元素中基数 r 是 10，即每位范围是 0~9，每一位都有 r 种取值； kⁱ 的值就是 0 ~9，k⁰ 是第1位（个位），k¹是第2位（十位），k²是第3位（百位）

基数排序得到 递减序列 的过程如下：

• 初始化：设置 r 个空队列，Q_r-1，Q_r-2，……，Q₀
• 按照各个 关键字位 权重递增的次序 （个，十，百），对 d 个关键字位分别做 “分配” 和 “收集”
• 分配：顺序扫描各个元素，若当前处理的关键字位 = x，则将元素插入 Q_n 队尾
• 收集：把 Q_r-1，Q_r-2，……，Q₀ 各个队列中的结点依次出队并链接

其实就是我们刚刚的过程书面化了。

还有就是，基数排序不是基于“比较”的算法，是基于“分配”和“收集”的算法

3.性能

显然我们基数排序需要用到队列，一般基于链式存储每一个队列结点（队列中每一个结点中有data和指向下一个结点的指针）

光有这些还不行，每个队列还得有一个队列的队头指针和队尾指针是吧，因为我们要执行入队出队操作嘛。

然后我们的基数 r 是几，就要设立几个辅助队列，比如我们刚刚 r是10，就 LinkQueue[10]，开个数组，这个也很容易理解

so综上所述，我们其实需要 r 个辅助队列，空间复杂度 = O( r )

一趟分配 O(n)，一趟收集 O( r )，总共 d 趟 分配、收集，总的时间复杂度 = O(d(n+r))

啥意思呢？就是比如我们上面说的，我们的元素最多三位数，所以第1趟个位，第2趟十位，第3趟百位，一共3趟；

每一趟我们要遍历每一个元素，对每一个元素我们都需要找到插入位置并插入队列，一共 n 个元素；

每一趟都有10个队列，我们要遍历每一个队列，我们要把各个队列进行出队，每个队列只需要被访问一次

所以每一趟都要先遍历元素（n个），再遍历队列（r个），一共 d 趟，so时间复杂度就是 O(d(n+r))

那么稳定性如何？

我们来看下面的栗子：

可以看到先遍历的元素分配的时候先入队，收集的时候先出队，所以 基数排序是稳定的。

4.应用

基数排序有什么应用咧？

举个栗子，如果某学校有 10000 个学生，将学生信息按照 年龄递减 排序，那如果用基数排序应该怎么搞？显然是比年月日是吧

所以 生日可以拆分为三组关键字：年（1995-2015），月（1-12），日（1-31），权重：年 > 月 > 日：

这样的话就比较好比了，这是个好方法。

为啥是个好方法？我们看看它好在哪：

刚刚的基数排序，我们一共有3趟，n个元素n是10000，最大的队列是日，最多31天，最多31个队列，所以刚刚的时间复杂度 = O(d(n+r)) ≈ O(30000)

如果我们采用 O(n²) 的排序，则约为 O(10⁸)，若采用 O(nlog₂n) 的排序，也约为 O(140000)，都老大了，还是基数排序时间复杂度最小。

但是我们怎么知道什么时候该用基数排序，有时候我们肉眼看也看不出来。

没想到吧，我们基数排序也有自己擅长解决的问题，归类如下：

1. 数据元素的关键字可以方便地拆分为 d 组，且 d 较小
2. 每组关键字的取值范围不大，即 r 较小
3. 数据元素个数 n 较大

什么意思呢？举个反例，比如第1个，说 d 要比较小，如果我们要给 5 个人的身份证号排序，那么我们 d 就要拆分为 18 组，因为身份证号有 18 位是吧，这样就不适合用，还不如直接比方便；

再比如第2个，我们数字倒是可以用，因为r是10，每位也就 0~9 ，范围不大。但是如果我们给中文姓名排序，那可就大了，列都列不完，虽然每个人的名字最多4个字，但是每个字范围太广，每个字都可能有上万种取值，也不适合基数排序；

最后比如第3个，像我们应用里举的那个栗子，给10000人的身份证号排序，刚刚我们不是看了吗，对于其他排序来说时间复杂度都比较高，基数排序时间复杂度比较好，其实就是因为我们元素太多了，所以元素个数比较多的时候其实是适合基数排序的。

总结

归并排序和基数排序都是稳定的。

第一篇插入排序中我们学的插入排序是稳定的，希尔排序是不稳定的；第二篇交换排序中我们学的冒泡排序是稳定的，快速排序是不稳定的；第三篇我们说到的选择排序中简单选择排序和堆排序都是不稳定的

归并是将几个有序的序列合成一个有序的序列，归并排序就是递归进行这个过程。

基数排序就是分为个位十位百位，先按照个位排序，再按照十位排序，再按照百位排序，它不是直接对比，是先分配再收集这样，还有要注意一下使用场景，有时候适合用基数排序，有时候不适合，其他就没什么了。