归并排序和基数排序

归并排序

归并排序与上述基于交换、选择等排序的思想不一样，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。假定待排序表含有 个记录，则可将其视为 个有序的子表，每个子表的长度为 1 ，然后两两归并，得到 个长度为 2 或 1 的有序表；继续两两归并如此重复，直到合并成一个长度为 的有序表为止，这种排序方法称为 2 路归并排序。

路归并，每选出一个元素需要对比关键字 次

Merge() 的功能是将前后相邻的两个有序表归并为一个有序表。设两段有序表 A[low..mid]、A[mid+1...high] 存放在同一顺序表中的相邻位置，先将它们复制到辅助数组 B 中。每次从对应 B 中的两个段取出一个记录进行关键字的比较，将较小者放入 A 中，当数组 B 中有一段的下标超出其对应的表长（即该段的所有元素都已复制到 A 中）时，将另一段中的剩余部分直接复制到 A 中。算法如下：

#include <cstdlib>
int n = A.length;
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 (i <= mid) {  // 处理剩余大值元素
        A[k++] = B[i++];
    }
    while (j <= high) {
        A[k++] = B[j++];
    }
}

注意：上面的代码中，最后两个 while 循环只有一个会执行。

一趟归并排序的操作是，调用 次算法 merge()，将 L[1...n] 中前后相邻且长度为 的有序段进行两两归并，得到前后相邻、长度为 的有序段，整个归并排序需要进行 趟。

递归形式的 2 路归并排序算法是基于分治的，其过程如下。

分解：将含有 个元素的待排序表分成各含 个元素的子表，采用 2 路归并排序算法对两个子表递归地进行排序。

合并：合并两个已排序的子表得到排序结果。

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);     // 归并
    }
}

2 路归并排序算法的性能分析如下：

空间效率：Merge() 操作中，辅助空间刚好为 个单元，所以算法的空间复杂度为 #card=math&code=O%28n%29&id=rWJZs) 。

时间效率：每趟归并的时间复杂度为 #card=math&code=O%28n%29&id=RQOF4)，共需进行 趟归并，所以算法的时间复杂度为 #card=math&code=O%28n%20%5Clog_%7B2%7D%7Bn%7D%29&id=hHAqm)。

稳定性：由于 Merge() 操作不会改变相同关键字记录的相对次序，所以 2 路归并排序算法是一种稳定的排序方法。

注意：一般而言，对于 个元素进行 路归并排序时，排序的趟数 满足 ，从而 ，又考虑到 为整数，所以 。这和前面的 2 路归并是一致的。

基数排序

基数排序是一种很特别的排序方法，它不基于比较和移动进行排序，而基于关键字各位的大小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

假设长度为 的线性表中每个结点 的关键字由 元组（）组成，满足 。其中 为主位关键字， 为最次位关键字。

为实现多关键字排序，通常有两种方法：

1. 最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。
2. 最低位优先（LSD）法，按关键字权重递增依次进行排序，最后形成一个有序序列。

下面描述以 为基数的最低位优先基数排序的过程，在排序过程中，使用 个队列 。基数排序的过程如下：对 ，依次做一次 “分配”和“收集”（其实是一次稳定的排序过程）。

1. 分配：开始时，把 各个队列置成空队列，然后依次考察线性表中的每个结点 #card=math&code=aj%20%5C%20%28j%3D0%20%2C%201%20%2C%20%5Ccdots%20%2C%20n-1%29&id=Nfmdc) ，若 的关键字 ，就把 放进 队列中。
2. 收集：把 各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。

基数排序算法的性能分析如下：

空间效率：趟排序需要的辅助存储空间为 （ 个队列： 个队头指针和r个队尾指针），但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为 #card=math&code=O%28r%29&id=JBSXT)。

时间效率：基数排序需要进行 趟分配和收集，一趟分配需要 #card=math&code=O%28n%29&id=Cxmfu)，一趟收集需要 #card=math&code=O%28r%29&id=mRT24) ，所以基数排序的时间复杂度为 )#card=math&code=O%28d%28n%2B%20r%29%29&id=ynNA1) ，它与序列的初始状态无关。

稳定性：对于基数排序算法而言，很重要一点就是按位排序时必须是稳定的。因此，这也保证了基数排序的稳定性。

基数排序擅长解决的问题：

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