1. 桶排序

关于桶排序，有两个参数

• 一个是需要排序数的范围M，表明范围是 0-M
• 另外一个是需要排序数的个数 N

其中第一个参数M表明了需要的桶的个数。

代码实现如下：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N=5;
    int M=100;
    int arr[N]={100,5,37,37,66};
    int bucket[M+1]={0};
    for(int i=0;i<N;i++){
        bucket[arr[i]]++;
    }
    for(int i=1;i<M+1;i++){
        if(bucket[i]==0){
            continue;
        }else{
            while(bucket[i]-->0){//为了处理有多个数重复的情况
                cout<<i<<" ";
            }
        }
    }
}

性能分析

时间复杂度O（M+N）

缺点

若M过大，则桶过多，占据的空间过大。

2. 基数排序

如果基数为10，则有10个桶；如果基数为2，则有两个桶。
基数是人为选定的。
详细见数P41，下文介绍几个要点。

使用简单数组的空间需求

如果使用简单数组来模拟桶，则每个数据大小必然为N，考虑所有的数都有某位数字的情况。
所以总的空间复杂度是O（N^2）

使用链表实现的时间需求分析

O（p（N+B））
P是排序的趟数，与要排序的最大的数在基数X的情况下有几位有关
N是要排序元素的个数
B是桶数，与基数有关。

缺点

虽然时间复杂度是O（N），但是有些大的常数会使得排序的趟数增加，从所用时间的增长速度（随着N的变化）超过O（NlogN），因为O（logN）增长的很慢。
从T（n）/f(n) =c 的角度考虑，表现为常数过大。

代码实现和头文件

linkedlist.h基数排序.cpp