桶排序算法（C语言实现）

桶排序法的基本思想：将数据分到有限数量的桶里，每个桶里的数再进行排序。简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的数再进行排序。

例如，对 [1，100] 范围内的 n 个整数 a[1，n] 进行排序，步骤如下。

• 将这类排序分为 3 个桶：第 1 个桶（数组 a）的整数范围为 [1，10]、第 2 个桶（数组 b）的整数范围为 [11，50]、第 3 个桶（数组 c）的整数范围为 [51，100]。
• 对这 n 个数进行从头到尾的扫描，将 1 到 10 之间的数放在数组 a 中，将 11 到 50 之间的数放在数组 b 中，将 51 到 100 之间的数放在数组 c 中。

示例

使用桶排序法对数列 [5，2，30，98，20，1，45，80] 从小到大排序。C语言编程代码如下：

#include<stdio.h>
int main()
{
    int m[8]={5,2,30,98,20,1,45,80};
    int a[10]={0};        /*数组a存放[1,10]的数,将数组a赋值为零*/
    int b[40]={0};        /*数组b存放[11,50]的数,将数组b赋值为零*/
    int c[50]={0};        /*数组c存放[51,100]的数,将数组c赋值为零*/
    int i;
    for(i=0;i<8;i++)
    {
    if((m[i]>0)&&( m[i]<11)) 
        a[m[i]-1]=1;               /*假如i=0,那么m[i]=5;将5放在数组a的第5个位置，即a[4]中,所以是a[m[i]-1] */
    if((m[i]>10)&&( m[i]<51)) 
        b[m[i]-10-1]=1;   
    if((m[i]>51)&&( m[i]<101)) 
        c[m[i]-50-1]=1;    
    }
    for(i=0;i<10;i++)                         /*输出数组a的结果*/
      if(a[i]==1)  printf(" %d  ",i+1);
    for(i=0;i<40;i++)                         /*输出数组b的结果*/
      if(b[i]==1)  printf(" %d  ",i+11);
    for(i=0;i<50;i++)                         /*输出数组c的结果*/
      if(c[i]==1)  printf(" %d  ",i+51);
    printf("\n");
}

运行结果:

1   2   5   20   30   45   80   98

本例定义了 3 个数组，分别存放 [1，10]、[1 1，50]、[51，100] 的数。将序列 m 中对应的数放在对应的数组中，并标记为 1。

例如，45 属于 [11，50] 之间的数，所以放在数组 b 中，数组 b 总共有 40 个元素，11 放在 b[0]、12 放在 b[1]……所以 45 应该放在 b[45-11]=b[34] 中。

将 m 中的数存放在对应的数组元素的过程，已经完成了从小到大的排序。

在输出结果的时候，只要数组 a、b、c 中的元素为 1，就表示这个元素的位置代表序列 M 中的数，所以只需要输出数组元素为 1 的位置上的数据即可。

声明：《C语言系列教程》为本站“54笨鸟”官方原创，由国家机构和地方版权局所签发的权威证书所保护。