1.桶排序
有N个整数,范围是1-M或者是0-M-1。留置一个数组Count,其大小为M,并初始化为0。于是Count有M个单元(或者叫桶)。当Ai被读入时,Count[Ai]增1。当所有的输入被读入,扫描Count,打印输出排序号的列表。桶排序实现代码如下:
- #include<stdio.h>
- #defineMax10
- voidinitArray(intarr[],intlen)
- {
- intk;
- for(k=0;k<len;k++)
- {
- arr[k]=0;
- }
- }
- voidPrintBucketArray(intBucketArr[],intlen)
- {
- intj;
- for(j=0;j<len;j++)
- {
- inttmp=BucketArr[j];
- while((tmp--)>0)
- {
- printf("%d\n",j);
- }
- }
- }
- voidBucketSort(intinput[],intla,intoutput[],intlb)
- {
- initArray(output,lb);
- inti;
- for(i=0;i<la;i++)
- {
- output[input[i]]++;
- }
- PrintBucketArray(output,lb);
- }
- intmain(void)
- {
- inta[10]={9,8,8,5,1,3,3,3,2,2};
- intb[Max];
- BucketSort(a,10,b,Max);
- return0;
- }
2.基数排序
基数排序是桶排序的推广:N个数位于0-NP-1之间(P是某个常数)。这种情况下就不适合使用桶排序了一次性搞定。既然不能一次搞定,可以考虑分步骤多次处理。基数排序的思路:每一趟对待排序的数的最低有效位进行桶排序。也就是说,先对每个数按照最低位进行桶排序,然后按照次低位桶排序……
举例是最好的说明。现在有10个数:64、8、216、512、27、729、0、1、343、125。10个数,都落在0-999(10^3-1)之间。
先按照最低位排序得到结果如下:
0 |
1 |
512 |
343 |
64 |
125 |
216 |
27 |
8 |
729 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
然后按照次低位排序,结果得到:
08 01 00 |
216
512
|
729
27
125
|
|
343 |
|
64 |
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
接着按照倒数第三位排序,结果:
064 027 008 001 000 |
125 |
216 |
343 |
|
512 |
|
729 |
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
基数排序代码之后再补上。
分享到:
相关推荐
基数排序/桶排序 *统计将数组中的数字分配到桶中后,各个桶中的数字个数 *数组中每个数的每一位数根据大小分配到对应大小为0~9的桶 *将各个桶中的数字个数,转化成各个桶中最后一个数字的下标索引
自己用C++写的桶式排序算法,是数据结构的一个作业题。。。
算法导论之基数排序,桶排序。基数排序是利用在各个位上进行计数排序,是一种线性排序
植物大战僵尸————铁桶僵尸
Java排序算法:插入,冒泡,选择,Shell,快速排序,归并排序,堆排序,桶式排序,基数排序
桶式排序法桶式排序法桶式排序法桶式排序法
植物大战僵尸————铁桶僵尸(啃食)
博客《数据结构与算法 —— 排序算法(3)》中的桶排序的时间复杂度计算公式推到过程。
VC++2012编程演练数据结构《32》桶排序
包括: 堆排序.swf 规并排序.swf 基数排序.swf 快速排序.swf 冒泡排序.swf 桶式排序法.swf 希尔排序.swf 直接插入排序.swf 直接选择排序.swf
数据结构之排序算法 包含目前所有排序方法: 1 快速排序 2 冒泡排序 3 堆排序 4 希尔排序 5 直接插入排序 6 直接选择排序 7 基数排序 8 箱、桶排序 9 归并排序
在这份文档中,我用C语言实现了排序算法的多种方法,包括插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序、桶排序和基数排序。这些算法可以帮助我们对数据进行有效的排序和整理,以便更好地处理和分析...
桶排序算法是常见排序里最快的一种,比快排还要快…可扩展。iOS版的桶排序算法,欢迎大家学习,交流~
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
数组应用之桶排序课件,用于信息学奥赛基础算法上课应用。课件内容讲解了桶排序的基本思想,问题应用,知识扩展及多维桶等。
插入排序 并归排序 桶排序 快速排序这些算法书上的经典算法,给出了算法过程,可供测试实际运行效率或者学习算法本身
本资源比较全面的包涵了各种排序,三种交换排序,选择排序,桶排序,归并排序,快速排序,二分法排序,等等
桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶排序.py 使用python代码实现桶...
最快的排序算法 最快的内部排序法—桶排序法,排序算法数据结构
包括插入排序、堆排序、归并排序、基数排序、快速排序、冒泡排序、桶排序、拓扑排序、希尔排序、选择排序。