桶排序
分類 算法
桶排序是計數排序的更新版。它利用了函數的映射關系,高效與否的關鍵就在于這個映射函數的确定。為了使桶排序更加高效,我們需要做到這兩點:
- 在額外空間充足的情況下,盡量增大桶的數量
- 使用的映射函數能夠将輸入的 N 個資料均勻的配置設定到 K 個桶中
同時,對于桶中元素的排序,選擇何種比較排序算法對于性能的影響至關重要。
什麼時候最快
當輸入的資料可以均勻的配置設定到每一個桶中。
什麼時候最慢
當輸入的資料被配置設定到了同一個桶中。
示意圖
元素分布在桶中:
代碼實作
JavaScript
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; // 輸入資料的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // 輸入資料的最大值
}
}
//桶的初始化
var DEFAULT_BUCKET_SIZE = 5; // 設定桶的預設數量為5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) {
buckets[i] = [];
}
//利用映射函數将資料配置設定到各個桶中
for (i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // 對每個桶進行排序,這裡使用了插入排序
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}
Java
public class BucketSort implements IArraySort {
private static final InsertSort insertSort = new InsertSort();
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝,不改變參數内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return bucketSort(arr, 5);
}
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函數将資料配置設定到各個桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 對每個桶進行排序,這裡使用了插入排序
bucket = insertSort.sort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
/**
* 自動擴容,并儲存資料
*
* @param arr
* @param value
*/
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}