归并排序和基数排序

归并排序

算法思想

1. “归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。
2. 假定待排序表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为1，然后两两归并，得到[n/2] (向上取整)个长度为2或1的有序表；继续两两归并…….如此重复，直到合并成一个长度为n的有序表为止。
3. Merge()的功能是将前后相邻的两个有序表归并为一个有序表。设两段有序表A[low…mid]、A[mid+1…high]存放在同一顺序表中的相邻位置，先将它们复制到辅助数组B中。每次从对应B中的两个段取出一个记录进行关键字的比较，将较小者放入A中，当数组B中有一段的下标超出其对应的表长（即该段的所有元素都已复制到A中）时，将另一段中的剩余部分直接复制到A中。
4. 一趟归并排序的操作是，调用[n/2h] (向上取整)次算法merge(),将L[1…n]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为 2h的有序段，整个归并排序需要进行[ log₂ⁿ ] (向上取整)趟。
5. 递归形式的2路归并排序算法是基于分治的，其过程如下：
   1. 分解：将含有n个元素的待排序表分成各含n/2个元素的子表，采用2路归并排序算法对两个子表递归地进行排序。
   2. 合并两个已排序的子表得到排序结果。

模板代码

ElemType *B = (ElemType *)malloc((n + 1) * sizeof(ElemType));   //辅助数组B
void Merge(ElemType A[],int low,int mid,int high){
    //表A的两段A[low...mid] 和 A[mid+1...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])                    //比较B的左右两段中的元素
            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循环只有一个会执行。

void MergeSort(ElemType 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);               //归并
    }//if
}

性能分析

1. 空间效率：Merge()操作中，辅助空间刚好为n个单元，所以算法的空间复杂度为O(n).
2. 时间效率：每趟归并的时间复杂度为O(n),共需进行[ log₂ⁿ ] 趟归并，所以算法的时间复杂度为O(nlog₂ⁿ).
3. 稳定性：由于Merge()操作不会改变相同关键字记录的相对次序，所以2路归并排序算法是一种稳定的排序方法。
4. 注意:一般而言，对于N个元素进行k路归并时，排序的趟数m满足 k^m = N ,从而 m = log_k^m,又考虑到m为整数，所以m = [ log_k^m ]。

基数排序

算法思想

1. 基数排序是一种很特别的排序方法，它不基于比较和移动进行排序，而基于关键字各位的大小进行排序
2. 假设长度为n的线性表中每个结点a_j的关键字由d元组(k_j^d-1,k_j^d-2,…,k_j¹,k_j⁰)组成，满足 0 <= k_jⁱ> <= r-1 (0 <= j < n,0 <= i <= d-1)。其中k_j^d-1为最主关键字，k_j⁰为最次关键字
3. 为实现多关键字排序，通常有两种方法：
   1. 第一种是最高位优先(MSD)法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。
   2. 第二种是最低位优先(LSD)法，按关键字位权重递增依次进行排序，最后形成一个有序序列。

性能分析：

1. 空间效率：一趟排序需要的辅助存储空间为r(r个队列：r个队头指针和r个队尾指针)，但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为O(r).
2. 时间效率：基数排序需要进行d趟分配和收集，一趟分配需要O(n),一趟收集需要O(r),所以基数排序的时间复杂度为O(d(n+r)),它与序列的初始状态无关。
3. 稳定性：对于基数排序算法而言，很重要一点就是按位排序时必须是稳定的。因此，这也保证了基数排序的稳定性。

题目总结

1. 插入排序和归并排序都不能保证在一趟排序结束后一定有元素放在最终的位置上。
2. 归并排序算法在平均情况下和最坏情况下的空间复杂度都会达到O(n),快速排序只在最坏情况下才会达到O(n),平均情况下为O(log₂ⁿ).
3. 选择排序的比较次数与序列初始状态无关，归并排序的比较次数的数量级也与序列的初始状态无关。
4. 归并排序代码比选择插入排序更复杂，前者的空间复杂度是O(n),后者是O(1)。但前者的时间复杂度是O(nlog₂ⁿ),后者是O(n²).