2022-WangDao-CS-DS-Notes/8.9基数排序（稳定）.md

基数排序——Radix Sort

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

r为基数，基数是每一位可以取的数的范围，例如10进制的一位数可以取0~9，则十进制的基数r=10。

d为关键字个数，也是趟数，例如10进制的一位数为一个d。

n为元素个数

基数排序擅长树立d小，r小，n大的元素序列进行排序。

一、算法思想：

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的

二、代码实现：

需一个辅助链队列来实现

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

三、算法效率分析

空间、时间复杂度取决于基数r

空间复杂度=$$O(r)$$， 因为需要r个辅助队列，链队列是增加指针域，则每个链队列的空间复杂度=O(1)

时间复杂度=O(d(n+r))

算法稳定性：稳定

四、基数排序的应用