基数排序（Radix Sort）

  • 平均时间复杂度：O(n×k)
  • 最好情况：O(n×k)
  • 最坏情况：O(n×k)
  • 空间复杂度：O(n+k)
  • 排序方式：外部

  • 稳定性：稳定

    C++代码实现

    1. int maxbit(vector<int>& arr) //辅助函数，求数据的最大位数
    2. {
    3.   int res=0,maxVal=*max_element(arr.begin(), arr.end());
    4.   while(maxVal){
    5.       res++;
    6.       maxVal/=10;
    7.   }
    8.   return res;
    9. }
    10. //基数排序
    11. void radixsort(vector<int>& arr) 
    12. {
    14.   int offset=0,minVal=*min_element(arr.begin(), arr.end());
    16.   if(minVal<0){
    17.       offset=-minVal;
    18.       for(auto& val:arr)
    19.           val+=offset;
    20.   }
    21.   queue<int> barrel[10];
    22.   int bit=maxbit(arr);
    23.   int div=1,len=arr.size();
    25.   for(int i=0;i<bit;i++){
    26.       for(int j=0;j<len;j++){
    27.           barrel[arr[j]/div%10].push(arr[j]);
    28.       }
    29.       vector<int>::iterator it=arr.begin();
    30.       for(int k=0;k<10;k++){
    31.           while(!barrel[k].empty()){
    32.               *it=barrel[k].front();
    33.               it++;
    34.               barrel[k].pop();
    35.           }
    36.       }
    37.   }
    39.   if(minVal<0){
    40.       offset=-minVal;
    41.       for(auto& val:arr)
    42.           val-=offset;
    43.   }
    44. }

1. 算法步骤

  1. 将整数按位数切割成不同的数字，然后按每个位数分别计数排序。
  2. 重复1到排序序列中数字最大值的位数次数

2. 动图演示

radixSort.gif