快速排序算法-桶排序介绍
文章目录
桶排序:
桶排序是一种效率很高的排序算法,它的时间复杂度为O(N+M),(N个元素,范围为0--M),但桶排序有一定的限制,必须为非负整数,而且元素不宜过大。
算法思想:
设待排序序列的元素取值范围为0到m,则我们新建一个大小为m+1的临时数组并把初始值都设为0,遍历待排序序列,把待排序序列中元素的值作为临时数组的下标,找出临时数组中对应该下标的元素使之+1;然后遍历临时数组,把临时数组中元素大于0的下标作为值按次序依次填入待排序数组,元素的值作为重复填入该下标的次数,遍历完成则排序结束序列有序。
简单举例:
假设有11个桶,编号从0~10。每出现一个数,就将对应编号的桶中的放一个小旗子,最后只要数数每个桶中有几个小旗子就OK了。例如2号桶中有1个小旗子,表示2出现了一次;3号桶中有1个小旗子,表示3出现了一次;5号桶中有2个小旗子,表示5出现了两次;8号桶中有1个小旗子,表示8出现了一次。

代码实现:
[Java]纯文本查看__复制代码
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class SortTest {
/**
* 桶排序,此处从小到大排序。
* 如果需要从到到小,只需逆向遍历桶索引
* @param data
* @param max
*/
public static void buktSort(`int[] data,int max){`
//创建并初始化桶的值
int`[] buket = new int`[max];
for`(int` `i=0`; i<max;i++){
buket[i]=`0`;
}
//将要排序的元素当做桶的索引,找到对应的桶位置,进行计数,
//即桶的索引为要排序的值,索引对应的位置的值为出现 的次数
for`(int` `i =0`; i<data.length; i++){
buket[ data[i] ]++;
}
//因为桶索引即为要排序的元素,而且索引本身就是从小到大排序的,
//所以从小到大输出桶索引,为0的不输出,大于1的按出现的次数依次输出,即能完成排序
for`(int` `i=0`; i<buket.length; i++){
for`(int` `j=0`; j<buket[i]; j++){
System.out.print(i + ","`);`
}
}
}
//桶排序测试
public static void main(String[] args) {
int`[] data = {1,0,10,3,5,6,6,8};`
SortTest.buktSort(data, 11`);`
}
}
以上代码在SortTest类中定义了buktSort方法,并对数组{1,0,10,3,5,6,6,8}进行从小到大排序
运行main方法后,控制台打印结果如下:
7.png(10.83 KB, 下载次数: 0)

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论