首页 > 编程笔记

桶排序算法(C语言实现)

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

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

示例

使用桶排序法对数列 [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 的位置上的数据即可。

优秀文章