C语言必学的12个排序算法：桶排序（第10篇）

今天药忘吃喽~ 2023-03-05 06:26 11阅读 0赞

# 基本思想 #

桶排序(bucket sort)，和计数排序（参见前一篇文章）有些类似，同样是线性排序算法，基本思想是将输入的待排序列n个整数数据元素，根据每个数据元素的取值范围\[0,k\]，划分称为m个区间，每个区间称为桶，每个桶存放该区间的数据元素，由于每个桶内的数据元素个数不确定，可以使用链表表示，同时使用插入排序，让每个桶的链表有序。这样按照次序将所有桶的元素连起来就得到完整的有序列表。

桶排序，和计数排序一样，对输入的数据元素有一定要求，需要根据数据元素特征容易划分桶，具体问题具体分析，以下均以常用的整数排序为例。

这里以整数排序为例子。例如有100个整数，每个整数取值范围\[000-999\]，备注：桶排序要求整数取值值是十进制位数相等。

计数排序，根据取值范围申请1000个元素的数组用于计数，当整数取值范围过大时，内存空间浪费严重；

桶排序可以将取值范围1000划分10个区间，例如百分位的十进制数字，划分10个区间，也就是10个桶，\[000-099\]-\[100-199\]…\[900-999\]，这样将待排的100个整数根据百分位数字分配到10个桶，每个桶指向链表的第一个结点，并且使用插入排序进行排序。

# 代码实现 #

1.区间划分，使用数组即可。

2.每个桶需要创建链表和进行链表插入排序。

/*
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node
    {
      int data;
      struct node *next;
    };
    // 对每个链表（桶）进行插入排序 
    void insert_node(struct node **bucket, int data)
    {
      struct node *p = (struct node *)malloc(sizeof(struct node));
      p->data = data;
      p->next = NULL;
      
      // 桶为空 
      if(*bucket == NULL)
      {
        *bucket = p;
      }else
      {
        struct node *pre = NULL;
        struct node *cur = *bucket;
        
        while(cur != NULL && cur->data <= data)
        {
          pre = cur;
          cur = cur->next;
        }
        // 对插入到第一个结点前的情况处理
        if(pre == NULL)
        {
          *bucket = p;
           p->next = cur;
        }else
        {       
          pre->next = p;
          p->next = cur;
        }
      } 
    }
    
    // k表示数据位数，3为表示取值范围[000-999] 
    void bucket_sort(int a[], int length, int k)
    {
      // 申请桶空间
      struct node **b = (struct node **)calloc(10,sizeof(struct node *));
      int i,j,m;
      // 将待排数据记录分配到桶 
      for(i=0; i<length; i++)
      {
        // 获取对应10个桶的标识 0-9 
        m = a[i];
        for(j=k; j>1; j--)
          m = m/10;
        // 分配到桶链表中
        insert_node(&b[m],a[i]); 
      }
      
      // 方便返回结果，复制到原数组a中 
      // 复制到数组a中
      struct node *p;
      for(i=0,j=0; i<10 && j<length; i++)
      {
        if(b[i] != NULL)
        {
          p = b[i];
          // 遍历每个桶元素 
          while(p != NULL)
          {
            a[j] = p->data;
            j++;
            p = p->next;
          } 
        }
        
      }
      // 释放存储空间
      for(i=0; i<10; i++)
      {
        while(b[i] !=NULL)
        {
          p = b[i];
          b[i] = p->next;
          free(p);
        } 
      }
      free(b);
    }
    
    
    int main(void)
    {
        int a[14] = {103,102,101,401,489,345,322,710,500,609,0,3,4,800};
        bucket_sort(a, 14, 3);
        int i;
        for(i=0; i<14; i++)
          printf("%d ", a[i]);
        return 0;
    }

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。  
![format_png][]  
![format_png 1][]

[format_png]: /images/20230208/d301a7a298a84ada9dbb8aa25f31137d.png
[format_png 1]: /images/20230208/74e1ca1f855d425ea48146a4a49651b9.png