桶排序是一種分配式排序算法，將元素分到有限數量的桶里，每個桶再單獨排序（比如用插入排序），最后依次把各個桶中的元素取出來即完成排序。

時間復雜度：最佳 O(n) | 平均 O(n + n2/k + k) | 最差 O(n2)

空間復雜度:O(n + k)

穩定性:穩定

應用場景/前提條件

• 適合均勻分布的數據
• 需要額外空間
• 可以與其他排序算法結合

介紹

桶排序（Bucket Sort）是一種分布式排序算法，核心思想是將數據分散到有限數量的桶中，然后對每個桶中的數據進行排序，最后將各個桶中的數據有序地合并起來。桶排序是計數排序的擴展版本，特別適合均勻分布的數據集。

桶排序的效率取決于數據分布的均勻性。在最佳情況下，桶排序的時間復雜度可以達到 O(n)，在特定場景下非常高效。桶排序結合了哈希表的思想，通過映射函數將元素分配到不同的桶中實現排序????????

算法步驟

1. 確定桶的數量和范圍，創建對應數量的桶（通常是數組或鏈表）
2. 根據映射函數將每個元素分配到對應的桶中
3. 對每個桶內的元素分別進行排序（可以使用任何排序算法）
4. 按照桶的順序將各個桶中的元素依次取出，組成有序序列

代碼實現如下（浮點類型）：
?

public static void main(String[] args) {float[] nums = {0.23f,1f,0.82f,0f,1.2f,999f};handleData(nums);for (Float num : nums){System.out.println( num+" ");}}public static void handleData(float[] nums){//獲取最大最小數float max = nums[0];float min = nums[0];for(float num : nums){if(num> max){max = num;}if(num<min){min = num;}}//初始化桶List<List<Float>> list = new ArrayList<>();for(int i = 0; i< nums.length;i++){list.add(new ArrayList<>());}//桶范圍設置int step = (int)Math.ceil((double)(max-min)/(nums.length));//將元素放入桶中for(float num : nums){int index = (int)(num - min) / step;//處理臨界桶if(index == nums.length){index--;}list.get(index).add(num);}//桶中元素排序for(List<Float> key: list){for(int i = 1; i< key.size(); i++){float key1 = key.get(i);int j = i-1;while(j>=0&&key.get(j)>key1){key.set(j+1, key.get(j));j--;}key.set(j+1, key1);}}//將元素重新放回數值中int i = 0;for(List<Float> key: list){for(Float index: key){nums[i++] = index;}}}

代碼實現如下（整數類型）：

public static void main(String[] args) {int[] nums = {2,6,6,8,9,7,3,4,44,15,22};handleData1(nums);for (int num : nums){System.out.println( num+" ");}}public static void handleData1(int[] nums){//獲取最大最小數int max = nums[0];int min = nums[0];for(int num : nums){if(num> max){max = num;}if(num<min){min = num;}}//初始化桶List<List<Integer>> list = new ArrayList<>();for(int i = 0; i< nums.length;i++){list.add(new ArrayList<>());}//桶范圍計算-最大值-最小值/數組長度，再向上取整int step = (int)Math.ceil((double)(max-min)/(nums.length));//將元素放入桶中for(int num : nums){int index = (num - min) / step;if(index == nums.length){index--;}list.get(index).add(num);}//桶中元素排序--插入算法for(List<Integer> key: list){for(int i = 1; i< key.size(); i++){int index=  key.get(i);int j = i-1;while(j>=0 && key.get(j)>index){key.set(j+1,key.get(j));j--;}key.set(j+1,index);}}//將元素重新放回數值中int i = 0;for(List<Integer> key: list){for(Integer index: key){nums[i++] = index;}}}

以上代碼實現是根據個人理解情況，按思路寫的實現流程，還要許多可優化的地方，如桶個數、桶的數據范圍，都是可以優化的顛；
注意實際的算法中，還需要注意特殊情況的處理，如算法題：
164. 最大間距 - 力扣（LeetCode）
個人算法題解如下：
?

if(nums.length <2){return 0;}int k = handleData(nums);if (k ==0){return 0;}//最大差值int num = 0;for(int i =0; i<nums.length-1; i++){if ((nums[i+1]-nums[i])>num){num = nums[i+1]-nums[i];}}return num;}public int handleData(int[] nums){//獲取最大最小數int max = nums[0];int min = nums[0];for(int num : nums){if(num> max){max = num;}if(num<min){min = num;}}if(max-min == 0){return 0;}//初始化桶List<List<Integer>> list = new ArrayList<>();for(int i = 0; i< nums.length;i++){list.add(new ArrayList<>());}//桶范圍設置int step = (int)Math.ceil((double)(max-min)/(nums.length));//將元素放入桶中for(int num : nums){//int index = (int)((num-min)/step*(backetCount-1));int index = (num - min) / step;if(index == nums.length){index--;}list.get(index).add(num);}//桶中元素排序for(List<Integer> key: list){for(int i = 1; i< key.size(); i++){if(key.get(i-1)>key.get(i)){Integer temp = key.get(i);key.set(i,key.get(i-1));key.set(i-1,temp);}}}//將元素重新放回數值中int i = 0;for(List<Integer> key: list){for(Integer index: key){nums[i++] = index;}}return 1;}