桶排序（Bucket Sort）原理是將待排序數(shù)據(jù)分配到有限數(shù)量的桶里，再對每個桶里的數(shù)據(jù)進行排序错敢，是一種線性時間排序算法秸讹。每一個桶（Bucket）代表一個區(qū)間范圍，里面可以承載一個或多個元素认轨。
- 第一步：創(chuàng)建桶，創(chuàng)建桶的數(shù)量等于待排序元素個數(shù)
- 第二步：確定各桶的區(qū)間跨度月培，因為最后一個桶只存放待排序數(shù)據(jù)中的最大值嘁字，因此
區(qū)間跨度 = (最大值 - 最小值) / (桶數(shù)量 - 1) - 第三步：遍歷待排序數(shù)據(jù)，將每個數(shù)據(jù)對號放入各桶中
- 第四步：對各桶內元素分別排序杉畜；
- 第五步：遍歷所有桶纪蜒，按順序輸出所有元素即為最終排序好的元素。
復雜度分析
時間復雜度：O(n)
Java 代碼實現(xiàn)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
public class BucketSort {
public static void sort(double[] data) {
if (data == null || data.length == 0) {
return;
}
// 獲取待排序數(shù)據(jù)中最大值和最小值此叠，計算出差值
double max = data[0];
double min = data[0];
for (int i = 0; i < data.length; i++) {
if (data[i] > max) {
max = data[i];
} else if (data[i] < min) {
min = data[i];
}
}
double d = max - min;
// 初始化桶纯续，桶數(shù)量等于待排序數(shù)據(jù)個數(shù)
int bucketNum = data.length;
ArrayList<LinkedList<Double>> bucketList = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
bucketList.add(new LinkedList<>());
}
// 遍歷待排序數(shù)據(jù)，將其放入對應桶中
for (int i = 0; i < data.length; i++) {
int num = (int) ((data[i] - min) * (bucketNum - 1) / d);
bucketList.get(num).add(data[i]);
}
// 每個桶執(zhí)行內部排序
for (int i = 0; i < bucketList.size(); i++) {
Collections.sort(bucketList.get(i));
}
// 輸出全部元素
int index = 0;
for (LinkedList<Double> list : bucketList) {
for (double element : list) {
data[index++] = element;
}
}
}
public static void main(String[] args) {
double[] data = {1.32, 1.68, 0.37, 1.16, 8.56, 3.25, 4.44, 6.54, 1.68, 2.66, 3.88, 5.49};
sort(data);
System.out.println(Arrays.toString(data));
}
}
運行結果
[0.37, 1.16, 1.32, 1.68, 1.68, 2.66, 3.25, 3.88, 4.44, 5.49, 6.54, 8.56]
說明：
(1) 查找待排序數(shù)據(jù)中的最大值8.56和最小值0.37，差值為8.19
(2) 確定桶數(shù)量：12（等于待排序數(shù)據(jù)個數(shù)）
(3) 確定各桶區(qū)間跨度：(8.56 - 0.37) / (12 - 1) = 0.75杆烁，各桶的區(qū)間范圍分別為
[0.37, 1.06) [1.06, 1.81) [1.81, 2.56) [2.56, 3.31) [3.31, 4.06) [4.06, 4.81) [4.81, 5.56) [5.56, 6.31) [6.31, 7.06) [7.06, 7.81) [7.81, 8.56) [8.56, 8.56]
(4) 遍歷待排序數(shù)據(jù)牙丽，將其放入對應桶中简卧，以1.32為例兔魂，(1.32 - 0.37) * (12 - 1) / 8.19 = 1.27...，取整得1举娩，將其放入第2個桶析校，其余入桶過程如下所示：
[] [1.32] [] [] [] [] [] [] [] [] [] []
[] [1.32, 1.68] [] [] [] [] [] [] [] [] [] []
[0.37] [1.32, 1.68] [] [] [] [] [] [] [] [] [] []
[0.37] [1.32, 1.68, 1.16] [] [] [] [] [] [] [] [] [] []
[0.37] [1.32, 1.68, 1.16] [] [] [] [] [] [] [] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16] [] [3.25] [] [] [] [] [] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16] [] [3.25] [] [4.44] [] [] [] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16] [] [3.25] [] [4.44] [] [] [6.54] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25] [] [4.44] [] [] [6.54] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 2.66] [] [4.44] [] [] [6.54] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 2.66] [3.88] [4.44] [] [] [6.54] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 2.66] [3.88] [4.44] [] [] [6.54] [] [] [8.56]
[0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 2.66] [3.88] [4.44] [5.49] [] [6.54] [] [] [8.56]
(5) 每個桶內執(zhí)行排序
[0.37] [1.16, 1.32, 1.68, 1.68] [] [2.66, 3.25] [3.88] [4.44] [5.49] [] [6.54] [] [] [8.56]
(6) 遍歷所有桶，按順序輸出
0.37, 1.16, 1.32, 1.68, 1.68, 2.66, 3.25, 3.88, 4.44, 5.49, 6.54, 8.56
