前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本文從最簡單的一個排序算法——桶排序開始，分析桶排序的實現思路，代碼實現，性能特點以及適用場景。

0、其他排序算法索引

1、桶排序思想

一個簡單例子：

對6個人的英語測試成績（1~10分）進行排序。假如分數是[6,5,8,8,10,9],用桶排序的思想就是準備10個桶，編號依次為1~10，將成績放入對應的桶中，例如6分放入6號桶，兩個8分放入8號桶...然后按照桶的標號順序逐一輸出（有就輸出，沒有就不輸出），這就是桶排序的基本思想。

事實上，這只是一個簡易版，試想一下，如果待排序的元素跨度范圍比較大，例如1~10000，是不是需要10000個桶？實際上這種情況下，一個桶里并非總放一個元素，很多時候一個桶里放多個元素。其實真正的桶排序和散列表有一樣的原理。

實際排序中，通常對每個桶中的元素繼續使用其他排序算法進行排序，所以更多時候，桶排序會結合其他排序算法一起使用。

2、桶排序代碼

在分析了桶排序的思想后，首先要知道待排序元素的范圍，以上述為例，聲明一個長度為10的數組作為10個桶，然后將成績逐一往桶中放時，該桶的值+1，最終輸出倒序輸出數組下標，數組每個位置的值為幾就輸出幾次，這樣就能實現基本的桶排序。

public class BucketSort {  private int[] buckets;  private int[] array;    public BucketSort(int range,int[] array){    this.buckets = new int[range];    this.array = array;  }    /*排序*/  public void sort(){    if(array!=null && array.length>1){      for(int i=0;i<array.length;i++){        buckets[array[i]]++;      }    }  }    /*排序輸出*/  public void sortOut(){    //倒序輸出數據    for (int i=buckets.length-1; i>=0; i--){      for(int j=0;j<buckets[i];j++){        System.out.print(i+"/t");      }          }  }}

測試代碼：

public class SortTest {  public static void main(String[] args) {    testBucketsSort();  }    private static void testBucketsSort(){    int[] array = {5,7,3,5,4,8,6,4,1,2};    BucketSort bs = new BucketSort(10, array);    bs.sort();    bs.sortOut();//輸出打印排序  }}

3、桶排序性能特點

桶排序實際上只需要遍歷一遍所有的待排元素，然后依次放入指定的位置。如果加上輸出排序的時間，就要遍歷所有的桶。因此桶排序的時間復雜度是O(n+m),n是待排元素的個數，m是桶的個數，也就是待排元素的范圍。這個算法算是相當快的排序算法了，但是空間復雜度比較大。

當待排元素的大小范圍比較大，但待排元素個數比較少時，空間浪費就比較嚴重，待排元素分布月均勻，空間利用率越高，事實上這種情況很少見。

通過以上性能分析，可以得出桶排序的特點：速度快且簡單，但同時空間利用率較低。當待排數據跨度很大時，空間利用率是無法忍受的。

4、桶排序適用場景

根據桶排序的特點，桶排序一般適用于一些特定的環境，比如數據范圍較為局限或者有一些特定的要求，比如需要通過哈希映射快速獲取某些值，需要統計每個數的數量。但是這一切都以確認數據的范圍為前提，如果范圍跨度過大，則考慮用其他算法。