写在前面
背景
小哼的班上只有5个同学，这5个同学分别考了5分、3分、5分、2分、8分(最高分10分)，接下来将分数按照从大到小排序，排序后的结果是：8 5 5 3 2 ，写一段程序，让计算机读入5个数然后将这5个数从大到小输出。
直接上代码
#include <stdio.h>
int main(int argc, const char * argv[]) {
int a[11];
//设置a[t]的默认值为0
for (int i=0; i<11; i++) {
a[i] = 0;
}
int t;
for (int i=0; i<5; i++) {
scanf("%d", &t);
a[t]++; //设置考t分的人数
}
for (int i=10; i>=0; i--) {
for (int j=0; j<a[i]; j++) {
printf("%d", i);
}
}
printf("\n");
return 0;
}
解读
最高分是10分，所以创建了11个元素的数组，其中a[t]=n; 表示考t分的有n人。
默认情况下a[t]=0;
根据输入的t值，使a[t]自增1;
然后通过对a[]的倒序遍历，如果a[t]为0，则不输出; 如果a[t]=n>0,则输入n次t;
变形
输入n个0~1000之间的整数，将它们从大到小排序。
#include <stdio.h>
int main(int argc, const char * argv[]) {
// insert code here...
int n;
scanf("%d", &n); //n表示要排序的数字个数
int a[1001];
//(1)
for (int i=0; i<1001; i++) {
a[i] = 0;
}
int t;
//(2)
for (int i=0; i<n; i++) {
scanf("%d", &t);
a[t] ++;
}
//(3)
for (int i=1000; i>=0; i--) {
for (int j=0; j<a[i]; j++) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}
时间复杂度
代码中标记(1)处，一共循环了M次，M为桶的个数。标记(2)处一共循环了N次，N为待排序数的个数，标记(3)处共循环了(M+N)次，所以总的时间复杂度是O(M+N+M+N)=O(2*(M+N))，忽略常数，最终桶排序的时间复杂度是O(M+N).
总结与反思
这是一个非常快的排序算法，但它不是真正的桶排序算法，真正的桶排序算法之后会讲。这篇讲的是简化版的桶排序算法，其本质还不能算是一个真正意义上的排序算法。看一个例子: 5个人的名字和分数：huhu 5分，哈哈 3分， xixi 5分，hengheng 5分， river 8分。请按照分数从高到低，输入他们的名字，如果用上面的简化版桶排序算法仅仅是把分数进行了排序，最终输入的仅仅是分数，但没有对名字进行排序。
期待下一节：冒泡排序。
