转自: http://blog.csdn.net/weiwenhp/article/details/8618500
桶排序的思想和基数排序有点类似,都要借助临时空间.基数排序是先映射到大小为10的计数数组中,然后再映射到大小等于待排序数组长度的临时数组中.
而桶排序就是直接整个足够大的临时数组,把待排序的元素全部映射过来.其索引为待排序元素数值.所以为了确定临时数组的大小得先算出数组中最大数.
简单桶排序
简单桶排序的缺点很明显
1.不能有重复的元素.
2.元素不能为负数.
int GetMaxVal(int* arr, int len) { int maxVal = arr[0]; for (int i = 1; i < len; i++) { if (arr[i] > maxVal) maxVal = arr[i]; } return maxVal; } void SimpleBucketSort(int* arr, int len) { int tmpArrLen = GetMaxVal(arr, len) + 1; //因为数组索引是从0开始,所以数组得是最大数加1 int* tmpArr = new int[tmpArrLen]; int i, j; for (i = 0; i < tmpArrLen; i++) tmpArr[i] = -1; //把临时数组的值全部赋予-1,如果赋予0的话待排序数组中有0值就不能排序了 for (i = 0; i < len; i++) tmpArr[arr[i]]++; for (i = 0, j = 0; i < tmpArrLen; i++) { if (tmpArr[i] != -1) { arr[j] = tmpArr[i]; j++; } } }
对于第2点我们无能为力,但对于第一点可以改进下.
改进的桶排序
因为临时数组的索引就是待排序数组元素的值了,所以临时数组中可以不必再存储元素的值了.此时先把临时数组全部赋值为0,当有元素映射过来时就加1,有重复有元素就大于1
public static void BucketSort(int[] arr, int len, int max) { int[] count = new int[max + 1]; for (int i = 0; i < len; i++) count[arr[i]]++; for (int i = 0, j = 0; i < count.Length; i++) { while (count[i] != 0) { arr[j] = i; j++; count[i]--; } } }
相关推荐
多趟桶式排序bucket sort。数据输入:有10个数,范围为0到999。 [root@lumotuwe] gcc cas.c -o cas [root@lumotuwe] ./cas 64 8 216 512 27 729 0 1 343 125
桶排序,顾名思义就是运用桶的思想来将数据放到相应的桶内,再将每一个桶内的数据进行排序,最后把所有桶内数据按照顺序取出来,得到的就是我们需要的有序数据,可以在线性时间O(n)内完成排序工作
桶排序算法是一种基于计数的排序算法,其基本思想是先扫描一遍待排序的序列,找出最大值和最小值,然后根据最大值和最小值确定桶的个数,并将每个元素分配到对应的桶中,最后将每个桶中的元素进行排序,然后依次输出...
MPI bucket排序代码 用于mpi联系 熟悉bucket排序
BucketSort为AlgorithmMan中的桶排序演示工具(这是可执行文件;需要.net 4.0支持;非源代码)。 原文:C#算法设计排序篇之10-桶排序(附带动画演示程序) 链接:...
桶排序是一种线性排序算法,这里我们来详解Bucket Sort桶排序算法及C++代码实现示例,需要的朋友可以参考下
桶排序的MPI实现。MPI implementation of bucket sort.
随机产生一定范围内的随机数,进行桶排序,然后二分查找任意个数的数。
经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - ...
主要介绍了C++桶排序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
JavaScript桶排序算法桶排序算法桶排序(Bucket sort)也称箱排序,是一个排序算法,工作的原理是将数组分到几个桶里,桶的数量可由排序数组最大值与
桶排序(Bucket Sort)是对基数排序的一个变种。在排序过程中没有用到计数数组,而是用不同的桶来暂时存储关键字。使用静态队列模拟桶,实现桶排序。
桶排序(Bucket Sort)是对基数排序的一个变种。在排序过程中没有用到计数数组,而是用不同的桶来暂时存储关键字。使用二维数组模拟桶。
桶排序(Bucket Sort) 环形排序(Circle Sort) 鸡尾酒排序(Cocktail Shaker Sort) 梳排序(Comb Sort) 计数排序(Counting Sort) 循环排序(Cycle Sort) 双重排序(Double Sort) 荷兰国旗排序(Dutch ...
桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳...
桶排序(Bucket Sort)的原理很简单,它是将数组分到有限数量的桶子里。 假设待排序的数组a中共有N个整数,并且已知数组a中数据的范围[0, MAX)。在桶排序时,创建容量为MAX的桶数组r,并将桶数组元素都初始化为0;将...
桶排序 在每个存储桶中使用 InsertionSort 的 BucketSort 算法的实现。 这个实现制作了 10 个范围相等的桶,然后将每个元素放入正确的桶中。 然后将元素放入桶中后,对每个桶运行 InsertionSort。 之后,将数据组合...
桶排序(Bucket Sort) 深度优先搜索(Depth-First Search, DFS) 广度优先搜索(Breadth-First Search, BFS) 二分查找(Binary Search) 线性查找(Linear Search) 素字符串匹配算法(Naive String Matching) ...