桶排序

void bucket_sort() // 桶排序
{
    for(int i = 0;   i < n ; i ++) s[q[i]] ++ ; // 用桶计数
    for(int i = 1;   i < N ; i ++) s[i] += s[i-1];
    for(int i = n-1; i >=0 ; i --) w[--s[q[i]]] = q[i];
    for(int i = 0 ;  i < n ; i ++) q[i] = w[i]; 

}

基数排序

时间复杂度

O(d(n+rd))，因为基于桶排序，所以无最好最坏时间复杂度。待排序数中最大值的树越大即运行效率越慢。

代码思想：

其基于桶排序，将执行R轮桶排序算法，R为待排序中最大数字的位数。
算法从个位、十位、百位…R位分别堆各个数进行桶排序，则将会逐渐变有序。
https://www.bilibili.com/video/BV1zF411G7AU/?spm_id_from=333.337.search-card.all.click&vd_source=102f6911b86737e3cb7f0ed4fca03b11

void radix_sort(int d, int r) // 基数排序 ， d为位数，r为进制
{   
    int radix = 1;
    for(int i = 1; i <= d; i ++)  // 遍历每一位
    {
        for(int j = 0 ; j < r ; j ++) s[j] = 0; // 十进制的话就是十个桶
        //细讲一下下面这行，假如待排序（3，2，11），在进行第二轮桶排序，即遍历十位数字时，由于3，2无十位，因此s[ q[j] / radix % r]中的q[j] / radix % r 等于0，意味着按照第一轮个位排序后的顺序，以此将2，3放入第0个桶
        for(int j = 0 ; j < n ; j ++) s[ q[j] / radix % r]++;
        for(int j = 1 ; j < r ; j ++) s[j] += s[j-1];
        for(int j = n-1 ; j >= 0 ; j --) w[--s[q[j] / radix % r]] = q[j];
        for(int j = 0 ; j < n ; j++) q[j] = w[j];

        radix =radix * 10;
    }
}