算法相关——Java排序算法之桶排序(一)

时间:2023-12-20 16:41:15

0. 前言

本文就是介绍一些常见的排序算法。排序是一个非常常见的应用场景,也是开发岗位面试必问的一道面试题,有人说,如果一个企业招聘开发人员的题目中没有排序算法题,那说明这个企业不是一个“正规”的企业,哈哈,虽然有点戏谑,但是也从侧面证明了排序算法的重要性。

本文将介绍的是常见排序算法中的桶排序。

1.  桶排序

1.1  基本思想

桶排序是所有排序算法中最快、也是最简单的排序算法。基本思想是在知道所有待排元素的范围后,准备和这个范围同样数量的桶,并将元素放在对应的桶中,如待排元素为{3,1,5,9,6,5,0},就要准备10个桶标号为0到9(代码中对应一个数组的下标),将每个元素放入对应桶中,再将所有元素按顺序输出(代码中则按顺序将数组i下标输出arrary[i]次),即为{0,1,3,5,5,6,9}。

1.2  代码实现

/*
*@author Calvin in http://blog.csdn.net/seu_calvin/article/details/54800413
*@date 2017/01/31
*/
public class Order { private int[] bucket;
private int[] array;
public Order(int range, int[] array){
this.array = array;
//准备一个range长度的桶
this.bucket = new int[range];
} //将数据置于桶中
public void sort() {
if(array!=null){
for(int i = 0; i < array.length; i++){
bucket[array[i]]++;
}
}
} //遍历桶,并得到每个桶中数n,并输出n次该桶下标
public void print() {
for(int i = 0; i < bucket.length; i++)
for(int j = 0; j < bucket[i]; j++)
System.out.println(i);
} public static void main(String[] args) {
int[] array = new int[]{3,1,5,9,6,5,0};
Order order = new Order(10,array);
order.sort();
order.print();
} }

输出结果略去了。

1.3  性能特点

桶排序包括遍历元素和遍历桶输出两个过程,因此时间复杂度为O(n+m),n为待排元素数,m为桶数。单单排序则时间复杂度为O(n)。而空间复杂度就比较大了,如果是排序1,100,10000三个数也要准备10000个桶的空间,因此桶排序虽简单且快,但不适合数据跨度较大的使用场景。而且桶排序是不稳定的。由于大多数排序场景不确定数据跨度,因此桶排序很少被使用。