桶排序是一种排序的思想,其实现包括计数排序和基数排序两种,冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序都是基于比较的排序,而桶排序提出了一种新的思路,即基于数据状态的排序。
(1) 得到无序数组的取值范围
(2) 根据取值范围"创建"对应数量的"桶"
(3) 遍历数组,把每个元素放到对应的"桶"中
(4) 按照顺序遍历桶中的每个元素,依次放到数组中,即可完成数组的排序。
"桶"是一种容器,这个容器可以用多种数据结构实现,包括数组、队列或者栈。
public static void bucketSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int[] bucket = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
int i = 0;
for (int j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) {
arr[i++] = j;
}
}
}