桶排序 类似于计数排序所创建的统计数组,桶排序需要创建若干个桶来协助排序。
每一个桶代表一个区间范围,里面可以承载一个或多个元素。
再分别对每个桶里的元素进行排序 最后对桶集合进行遍历输出的就是有序数组
体现了分治思想
public void bucketSort(int[] array) {
int size = array.length;
int max = array[0], min = array[0];
for (int i = 1; i < size; i++) {
if (array[i] > max) max = array[i];
if (array[i] < min) min = array[i];
}
int bucketNum = size;//桶的数量
ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
bucketList.add(new LinkedList<>());
}
for (int i = 0; i < size; i++) {
//放到哪个桶
int num = (array[i] - min) * (bucketNum - 1) / (max - min);//重点
bucketList.get(num).add(array[i]);
}
for (int i=0;i<bucketNum;i++){
Collections.sort(bucketList.get(i));
}
int index = 0;
for (int i=0;i<bucketNum;i++){
System.out.println("桶"+i+"的元素数量:" + bucketList.get(i).size());
for (int n:bucketList.get(i)){
array[index++] = n;
}
}
}
其中
int num = (array[i] - min) * (bucketNum - 1) / (max - min); =偏移量 * (桶数量-1) / 差值 =偏移量 / ( 差值 / (桶数量-1) )
而 差值/(桶数量-1) 就是求出每个桶区间长度的公式
也就是说 取具体放到哪个桶的索引值的方法就是拿该元素的偏移量除以区间长度
每个桶中使用了jdk的归并排序。区间划分的越细,即桶的数量越多,理论上分到每个桶中的元素就越少,桶内数据的排序就越简单,其时间复杂度就越接近于线性。
极端情况下,就是区间小到只有1,即桶内只存放一种元素,桶内的元素不再需要排序,因为它们都是相同的元素,这时桶排序差不多就和计数排序一样了。