排序算法c语言描述 |
您所在的位置：网站首页 › 字符串排序c语言代码 › 排序算法c语言描述 |
排序算法c语言描述
|
十一。桶排序
一。个人理解
桶排序是另外一种以O(n)或者接近O(n)的复杂度排序的算法. 它假设输入的待排序元素是等可能的落在等间隔的值区间内.一个长度为N的数组使用桶排序, 需要长度为N的辅助数组. 等间隔的区间称为桶, 每个桶内落在该区间的元素. 桶排序是基数排序的一种归纳结果。 算法的主要思想: 待排序数组A[1...n]内的元素是随机分布在[0,1)区间内的的浮点数.辅助排序数组B[0....n-1]的每一个元素都连接一个链表.将A内每个元素乘以N(数组规模)取底,并以此为索引插入(插入排序)数组B的对应位置的连表中. 最后将所有的链表依次连接起来就是排序结果. 这个过程可以简单的分步如下: 设置一个定量的数组当作空桶子。寻访序列，并且把项目一个一个放到对应的桶子去。对每个不是空的桶子进行排序。从不是空的桶子里把项目再放回原来的序列中。例如要对大小为[1..1000]范围内的n个整数A[1..n]排序，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储(10..20]的整数，……集合B[i]存储((i-1)*10, i*10]的整数，i = 1,2,..100。总共有100个桶。然后对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。
代码如下。 #include #define Max_len 10 //数组元素个数 // 打印结果 void Show(int arr[], int n) { int i; for ( i=0; i maxVal) maxVal = arr[i]; } return maxVal; //返回最大值 } //桶排序 参数：数组及其长度 void BucketSort(int* arr , int len) { int tmpArrLen = GetMaxVal(arr , len) + 1; int tmpArr[tmpArrLen]; //获得空桶大小 int i, j; for( i = 0; i < tmpArrLen; i++) //空桶初始化 tmpArr[i] = 0; for(i = 0; i < len; i++) //寻访序列，并且把项目一个一个放到对应的桶子去。 tmpArr[ arr[i] ]++; for(i = 0, j = 0; i < tmpArrLen; i ++) { while( tmpArr[ i ] != 0) //对每个不是空的桶子进行排序。 { arr[j ] = i; //从不是空的桶子里把项目再放回原来的序列中。 j++; tmpArr[i]--; } } } int main() { //测试数据 int arr_test[Max_len] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 }; //排序前数组序列 Show( arr_test, Max_len ); //排序 BucketSort( arr_test, Max_len); //排序后数组序列 Show( arr_test, Max_len ); return 0; } 二。举例说明假如待排序列K= {49、38 、35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶，然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序后得到如下图所示：
对上图只要顺序输出每个B[i]中的数据就可以得到有序序列了。
桶排序动画 注： 这个例子摘录的时候太急了。没保存好网址，对原作者表示歉意，无法给出链接了。 再来一个例子。 该例子也是别人的。 来源： http://www.cnblogs.com/kkun/archive/2011/11/23/2260267.html 无序数组有个要求,就是成员隶属于固定(有限的)的区间,如范围为[0-9](考试分数为1-100等) 例如待排数字[6 2 4 1 5 9] 准备10个空桶,最大数个空桶 [6 2 4 1 5 9] 待排数组 [0 0 0 0 0 0 0 0 0 0] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在)
1,顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,这个过程类似这样:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ] [6 2 4 1 5 9] 待排数组 [0 0 0 0 0 0 6 0 0 0] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在)
2,顺序从待排数组中取出下一个数字,此时2被取出,将其放入2号桶,是几就放几号桶 [6 2 4 1 5 9] 待排数组 [0 0 2 0 0 0 6 0 0 0] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在)
3,4,5,6省略,过程一样,全部入桶后变成下边这样 [6 2 4 1 5 9] 待排数组 [0 1 2 0 4 5 6 0 0 9] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在)
0表示空桶,跳过,顺序取出即可:1 2 4 5 6 9 
差不多介绍到这里了。还是强调一下，因为我自己的学习过程也是通过看网上的资料，所以学习的也不够系统，如果讲的不够详细，下面给出了我学习过程中的一些资料，可以看看。
注：先标注，便于以后自己学习。 csdn博客 (四)分配排序:桶排序(Bucket Sort) 博客园 经典排序算法 - 桶排序Bucket sort 桶排序 维基百科 csdn博客排序算法——桶排序 算法总结系列之六: 桶排序(Bucket Sort) 桶排序 百度百科 |
【本文地址】
今日新闻 |
推荐新闻 |