桶排序算法的理解及C语言版代码示例

概述理解：桶排序是计数排序的变种，把计数排序中相邻的m个\"小桶\"放到一个\"大桶\"中，在分完桶后，对每个桶进行排序（一般用快排），然后合并成最后的结果。

理解：
桶排序是计数排序的变种，把计数排序中相邻的m个"小桶"放到一个"大桶"中，在分完桶后，对每个桶进行排序（一般用快排），然后合并成最后的结果。
基本思想：
桶排序假设序列由一个随机过程产生，该过程将元素均匀而独立地分布在区间[0,1)上。我们把区间[0,1)划分成n个相同大小的子区间，称为桶。将n个记录分布到各个桶中去。如果有多于一个记录分到同一个桶中，需要进行桶内排序。最后依次把各个桶中的记录列出来记得到有序序列。
效率分析：
桶排序的平均时间复杂度为线性的O(N+C)，其中C为桶内快排的时间复杂度。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。
桶排序的缺点是如果只排几个数，但是数字的范围却非常大（10个数，数的范围再0~10000000），那么我们需要10000001个桶才可以，即便是10个数。

举例
问题1：随机输入 5 个数，从大到小输出。
思路：借助一个根据输入数字最大值和最小值的范围数组，每当输入一个数字的时候，将数字插入对应数组的序号。

#include <stdio.h>int main(){ int a[11],i,j,t; //初始化桶数组 for(i=0;i<=10;i++) {   a[i] = 0; } //循环读入5个数 for(i = 1;i<=5;i++) {   //把每一个数读到变量中去   scanf("%d",&t);   //计数     a[t]++; } //从大到小输出 for(i = 10;i>=0;i--) {   for(j=1;j<=a[i];j++)     printf("%d",i); } getchar();getchar(); //getchar()用来暂停程序，以便查看程序输出的内容 //也可以用system("pause");来代替 return 0;}

问题2：对0-1000的整数进行排序

#include<stdio.h>int main(){ int book[1001],t; //初始化桶数组 for(i=0;i<=1000;i++) {   book[i] = 0; } //输入一个数n，表示接下来有n个数 scanf("%d",&n); for(i = 1;i<=n;i++) {   //把每一个数读到变量中去   scanf("%d",&t);   //计数     book[t]++; } //从大到小输出 for(i = 1000;i>=0;i--) {   for(j=1;j<=book[i];j++)     printf("%d",i); } getchar();getchar(); return 0;}

总结

以上是内存溢出为你收集整理的桶排序算法的理解及C语言版代码示例全部内容，希望文章能够帮你解决桶排序算法的理解及C语言版代码示例所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。