本文共 1208 字，大约阅读时间需要 4 分钟。

基数排序 -

桶排序的改进版，桶的大小固定为10，减少了内存空间的开销。首先，找出待排序列中得最大元素max，并依次按max的低位到高位对所有元素排序；桶元素10个元素的大小即为待排序数列元素对应数值为相等元素的个数，即每次遍历待排序数列，桶将其按对应数值位大小分为了10个层级，桶内元素值得和为待排序数列元素个数。

时间复杂度：O(x*N) 　　稳定性：稳定

/*基数排序*///1. 计数排序，按整形数值单位进行排序void countSort(vector
   
     &arr, int exp){
       int bucket[10] = {
    0 };    int arrSize = arr.size();    int *pTemp = new int[arrSize];    memset(pTemp, 0, arrSize * sizeof(int));    //统计单位exp各数值计数值    for (auto const val : arr)        ++bucket[(val / exp) % 10];    //计数分层    for (int i = 1; i < 10; ++i)        bucket[i] += bucket[i - 1];    //按exp位大小用数组arr元素填充pTemp    for (int i = arrSize - 1; i >= 0; --i)        pTemp[ --bucket[(arr[i] / exp) % 10] ] = arr[i];/*bugs*/#if 0    //bug1: bucket各层次的计数值没遍历一次相应自减1    for (auto const val : arr)        pTemp[bucket[(val / exp) % 10] - 1] = val;    //bug2: arr数组元素每次排序时，下标应从大到小遍历，否则无法实现排序    for (auto const val : arr)        pTemp[ --bucket[(val / exp) % 10] ] = val;#endif    //pTemp -> arr    for (int i = 0; i < arrSize; ++i)        arr[i] = pTemp[i];    delete []pTemp;}//2. 合并各单位计数排序结果void radixSort(vector
    
      &arr){
       int max = getMaxValue(arr);    for (int exp = 1; max / exp != 0; exp *= 10)        countSort(arr, exp);}
    
   

转载地址：http://simqf.baihongyu.com/