快速排序算法-桶排序介绍

桶排序:

桶排序是一种效率很高的排序算法,它的时间复杂度为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)

7.png

评论

暂无评论