桶排序

桶排序，其大概原理如下。。。（这是对于没有负数的情况）

如需要排序的值为 a[] = { 10, 4，20, 10, 50 ,100 }；

100为其中的最大值，所以我们需要开一个 101大的数组，也就是桶的数量。

还需要一个  num 数组来记录 每个数出现的次数，//不要num 一样的，num[] == 0 ， 就代表没有出现咯

for(0 to n)           //n 代表排序的数的个数
    num[a[i]] ++;    //意思是 a[i] 这个值出现的次数
    bucket[a[i]] = 1;     //标记这个数，代表他有出现.

最后在遍历一遍 0 到 100 (显然这一次的 i 代表的是值)， 如果  num[i] > 0, 就一次放入 s 数组 (s 代表排序后的数组).

其最好的时间复杂度为 O(n), 不过需要的空间比较大。。

代码：

///设最大值为 maxx < 100000， 元素的数量为 n < 100000

int num[100000 + 10];
int a[100000];         
int s[100000];

void bucket_sort(){
    int maxx = -1;
    for(int i = 0;i < n;i ++){
        if(maxx < a[i])
            maxx = a[i];
        num[a[i]] ++;
    }
    
    int ps = 0;
    for(int i = 0;i < maxx + 1;i ++){
        for(int j = 0;j < num[i];j ++)
            s[ps ++] = i;
    }
    
    for(int i = 0;i < ps;i ++)
        printf("%d ",s[i]);
}

 

而对于有负数的情况，就需要再添加一个 是否是负数的标志。。。 最后遍历的时候   先 for 一遍 maxx 到 0，因为是负数，所以要倒着 for， 如果 num[]  不是0 且  有负数标志， 就输出。   倒着for 完后，在正在 for 输出正数