桶排序

算法
2014-11-11
桶排序, 是最快最简单的排序。
标签: 桶排序 算法


桶排序, 是最快最简单的排序。有多宽维度,就要申请多大的数组。比如100分的试卷,就要申请101个数组(试卷是0-100分),有人考了100分,就把array[100]加1,有人考了90,就把array[90]加1,有人考了70,就把array[70]+1,又有人考了90,就把array[90]加1,那么从高到底打印,如果是某个分数是0个人,就不打印,如果某个分数是1个人,就打印一次,如果某个分数是2个人,就打印两次,上面的例子就是100,90,90,90,70。

桶排序快是毋庸置疑的,但是,浪费了空间。比如打游戏,新手村里的小鸡攻击力是1,而最后一个副本的大BOSS的攻击力是999999999,那么就要对这个游戏的所有玩家和怪物的攻击力排序,就要申请一个1000000000长度的数组,就是array[1000000000]。假如每个字段的值都是1,1是整形,需要是4-8个字节(到底是4还是8取决于机器),那么这个数组就是1000000000/8/1024/1024=119MB。嗯哼?一个数组就要119M,你就是13年淘宝双11的160G内存的机器也拖不起吧。

桶排序的时间复杂度是O(M+N),是最快的排序,它也是最简单的排序。


C语言代码:


#include

int main(){

int i, j, num, score, rank[100];

for(i=0; i<101; i++){

rank[i] = 0;

}

//需要录入多少个数据

printf("How many?\n");

scanf("%d", &num);

for(i=0; i

printf("Enter Score:\n");

scanf("%d", &score);

//我们的试卷是0-100分的哦

if(score<0 || score > 100){

printf("Error");

return 1;

}

//进桶

rank[score]++;

score = 0;

}

printf("Rank:\n");

//打印

for(i=0; i<101; i++){

for(j=0; j

printf("%d,", i);

}

}

}