程序员的核心技能之一就是算法,谈到算法,似乎都是从排序开始。对一组已知范围的数据进行排序,最快的算法是什么呢?快速排序?希尔排序?非也,非也~是本文的主角“桶排序”!
  来看一个实际例子吧:已知一组范围在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个数进行排序,这太浪费空间了!所以在选择使用哪种排序算法之前,还是需要根据实际情况,权衡好复杂度与空间的问题。
  

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