归并排序

2路归并的“归并树”——倒立的二叉树，树高h，归并排序趟数m = h-1，第h层最多2^(h-1)个结点，则满足n ≤ 2^(h-1)，即h-1 = ⌈log₂n⌉; 结论: n个元素进行2路归并排序，归并趟数 m = ⌈log₂n⌉

每趟归并时间复杂度为O(n), 算法总时间复杂度为O(nlog₂n);

空间复杂度为O(n); (归并排序算法可视为本章占用辅助空间最多的排序算法)

稳定性：归并排序是稳定的

对于N个元素进行k路归并排序，排序的趟数m满足 k^m = N, m = ⌈logkN⌉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//创建辅助数组B
int *B=(int *)malloc(n*sizeof(int));

//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++];
    }//for
     
    //没有归并完的部分复制到尾部，while只会执行一个 
    while(i<=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);     //归并
    }
}

基数排序

用于处理链式存储

  • 数据元素的关键字可以很容易地进行拆分成d组，且d较小；
  • 每组关键字的取值范围不大，即r较小；
  • 数据元素个数n较大。

总排序的时间复杂度为O(d(n+r))