1.桶排序
有N个整数,范围是1-M或者是0-M-1。留置一个数组Count,其大小为M,并初始化为0。于是Count有M个单元(或者叫桶)。当Ai被读入时,Count[Ai]增1。当所有的输入被读入,扫描Count,打印输出排序号的列表。
桶排序实现代码如下:
#include <stdio.h>
#define Max 10
void initArray(int arr[], int len)
{
int k;
for(k = 0; k < len; k++)
{
arr[k] = 0;
}
}
void PrintBucketArray(int BucketArr[], int len)
{
int j;
for(j = 0; j < len; j++)
{
int tmp = BucketArr[j];
while((tmp--) > 0)
{
printf("%d\n",j);
}
}
}
/************************************************
*桶排序,输入数组中的数不超过在0-Max-1之间
*
************************************************/
void BucketSort(int input[], int la, int output[], int lb)
{
initArray(output,lb);
int i;
for(i = 0; i < la; i++)
{
output[input[i]]++;
}
PrintBucketArray(output,lb);
}
int main(void)
{
int a[10] = {9,8,8,5,1,3,3,3,2,2};
int b[Max];
BucketSort(a,10,b,Max);
return 0;
}
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代码实现桶...
最快的排序算法 最快的内部排序法—桶排序法,排序算法数据结构
包括插入排序、堆排序、归并排序、基数排序、快速排序、冒泡排序、桶排序、拓扑排序、希尔排序、选择排序。