写在前面

背景

小哼的班上只有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分。请按照分数从高到低，输入他们的名字，如果用上面的简化版桶排序算法仅仅是把分数进行了排序，最终输入的仅仅是分数，但没有对名字进行排序。
期待下一节：冒泡排序。