有趣的桶排序

程序员的核心技能之一就是算法，谈到算法，似乎都是从排序开始。对一组已知范围的数据进行排序，最快的算法是什么呢？快速排序？希尔排序？非也，非也~是本文的主角“桶排序”！
　　来看一个实际例子吧：已知一组范围在0~10的数据(如:9,5,2,7,7),你有没有什么好方法编写一段程序，将数据从大到小输出呢？
　　看到这样的题目，相信很多人第一反应跟我一样，就是将这些数据进行比较，然后进行位置的交换，最终实现排序。可桶排序彻底颠覆了这种想法——第一次看到桶排序时，确实被惊艳到了——还有这种操作？！原来排序不一定非得老老实实对原有数据进行位置调整！
　　好了，回到我们的题目。我们只需要借助一个一维数组就可以解决问题。首先，我们申请一个长度为11的数组int a[11],因为我们的数据范围是0~10，而int a[11]的元素正好是a[0]~a[10]。开始的时候，我们将所有元素都初始化为0，表示这些数都未出现过。例如a[0]等于0，就表示待排序数据还未出现过0；同理，若a[9]等于1，则表示待排数据中9出现过1次。
　　有了上面的说明，那接下来就非常简单了，我们只需要遍历待排数组，然后将每个数值对应下标的元素加1(比如第一个数是9，我们就将a[9]加1)。你会发现，待排数组遍历完之后，a[0]~a[10]中的数值，其实就是0~10出现的次数，我们只需要按次数将下标打印出来就实现排序了。代码如下:

#include <stdio.h>
int main()
{
    int a[11],i,j,t;
    for(i=10; i>=0; i--)
    {
        a[i]=0;
    }

    for(i=1; i<=5; i++) //循环读入5个待排数
    {
        scanf("%d",&t); //把每一个数读到变量t中
        a[t]++; //进行计数
    }

    for(i=10; i>=0; i--)
    {
        for(j=1; j<=a[i];j++)
        {
            printf("%d ",i);
        }
    }

    printf("\r\n"); 
    getchar();  
    return 0;
}

执行该程序，我们可以随意输入5个0~10的数字，然后程序会将其按从大到小排序输出，如下图：

图1
　　接下来我们来看看时间复杂度。首先我们用了一个m次(m为桶的个数)的循环把桶清空;然后再用一个n次(n为待排序数据的个数)的循环，设置的数据的显示次数;最后又进行了m+n次循环，把数据显示出来。所以，整个排序算法一共执行了m+n+m+n次。我们用大写字母O来表示时间复杂度，因此该算法的时间复杂度是O(m+n+m+n)即O(2*(m+n))。我们在说时间复杂度的时候可以忽略较小的常数，最终桶排序的时间复杂度为O(m+n)。还有一点，在表示时间复杂度的时候，n和m通常用大写字母即O(M+N),这是一个非常快的排序算法。
　　桶排序虽快，但其实它是用空间在换时间。如果需要排序的数范围非常宽，那我们就需要申请非常多的“桶”来存储每一个数出现的次数。即使依然只是需要对5个数进行排序，这太浪费空间了！所以在选择使用哪种排序算法之前，还是需要根据实际情况，权衡好复杂度与空间的问题。

参考书籍：《啊哈！算法》
说明：本文所提到的是简化版的桶排序算法，真正的同排序算法要复杂些，有兴趣的朋友可以自行搜索学习。