桶式排序不再是一種基于比較的排序方法，它是一種比較巧妙的排序方式，但這種排序方式需要待排序的序列滿足以下兩個特征：

待排序列所有的值處于一個可枚舉的范圍之類；

待排序列所在的這個可枚舉的范圍不應該太大，否則排序開銷太大。

排序的具體步驟如下：

（1）對于這個可枚舉范圍構建一個buckets數組，用于記錄“落入”每個桶中元素的個數；

（2）將（1）中得到的buckets數組重新進行計算，按如下公式重新計算：

buckets[i] = buckets[i]+buckets[i-1] (其中1<=i<buckets.length);

桶式排序是一種非常優秀的排序算法，時間效率極高，它只要通過2輪遍歷：第1輪遍歷待排數據，統計每個待排數據“落入”各桶中的個數，第2輪遍歷buckets用于重新計算buckets中元素的值，2輪遍歷后就可以得到每個待排數據在有序序列中的位置，然后將各個數據項依次放入指定位置即可。

桶式排序的空間開銷較大，它需要兩個數組，第1個buckets數組用于記錄“落入”各桶中元素的個數，進而保存各元素在有序序列中的位置，第2個數組用于緩存待排數據。

桶式排序是穩定的。

如果待排序數據的范圍在0~k之間，那么它的時間復雜度是O(k+n)的

桶式排序算法速度很快，因為它的時間復雜度是O(k+n)，而基于交換的排序時間上限是nlgn。

但是它的限制多，比如它只能排整形數組。而且當k較大，而數組長度n較小，即k>>n時，輔助數組C[k+1]的空間消耗較大。

當數組為整形，且k和n接近時, 可以用此方法排序。（有的文章也稱這種排序算法為“計數排序”）

代碼實現：

public class BucketSortTest {      public static int count = 0;        public static void main(String[] args) {            int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };          PRint(data);          bucketSort(data, 0, 10);          print(data);        }        public static void bucketSort(int[] data, int min, int max) {          // 緩存數組          int[] tmp = new int[data.length];          // buckets用于記錄待排序元素的信息          // buckets數組定義了max-min個桶          int[] buckets = new int[max - min];          // 計算每個元素在序列出現的次數          for (int i = 0; i < data.length; i++) {              buckets[data[i] - min]++;          }          // 計算“落入”各桶內的元素在有序序列中的位置          for (int i = 1; i < max - min; i++) {              buckets[i] = buckets[i] + buckets[i - 1];          }          // 將data中的元素完全復制到tmp數組中          System.arraycopy(data, 0, tmp, 0, data.length);          // 根據buckets數組中的信息將待排序列的各元素放入相應位置          for (int k = data.length - 1; k >= 0; k--) {              data[--buckets[tmp[k] - min]] = tmp[k];          }      }        public static void print(int[] data) {          for (int i = 0; i < data.length; i++) {              System.out.print(data[i] + "/t");          }          System.out.println();      }    }  

　　運行結果：

5    3    6    2    1    9    4    8    7    1    2    3    4    5    6    7    8    9    

基數排序，說白了就是進行多次的桶式排序。

基數排序已經不再是一種常規的排序方式，它更多地像一種排序方法的應用，基數排序必須依賴于另外的排序方法。基數排序的總體思路就是將待排序數據拆分成多個關鍵字進行排序，也就是說，基數排序的實質是多關鍵字排序。

多關鍵字排序的思路是將待排數據里德排序關鍵字拆分成多個排序關鍵字；第1個排序關鍵字，第2個排序關鍵字，第3個排序關鍵字......然后，根據子關鍵字對待排序數據進行排序。

多關鍵字排序時有兩種解決方案：

最高位優先法（MSD）(Most Significant Digit first)

最低位優先法（LSD）(Least Significant Digit first)

例如，對如下數據序列進行排序。

192,221,12,23

可以觀察到它的每個數據至多只有3位，因此可以將每個數據拆分成3個關鍵字：百位（高位）、十位、個位（低位）。

如果按照習慣思維，會先比較百位，百位大的數據大，百位相同的再比較十位，十位大的數據大；最后再比較個位。人得習慣思維是最高位優先方式。

如果按照人得思維方式，計算機實現起來有一定的困難，當開始比較十位時，程序還需要判斷它們的百位是否相同--這就認為地增加了難度，計算機通常會選擇最低位優先法。

基數排序方法對任一子關鍵字排序時必須借助于另一種排序方法，而且這種排序方法必須是穩定的。

對于多關鍵字拆分出來的子關鍵字，它們一定位于0-9這個可枚舉的范圍內，這個范圍不大，因此用桶式排序效率非常好。

對于多關鍵字排序來說，程序將待排數據拆分成多個子關鍵字后，對子關鍵字排序既可以使用桶式排序，也可以使用任何一種穩定的排序方法。

代碼實現：

package 基數排序;import java.util.Arrays;public class MultiKeyRadixSortTest {        public static void main(String[] args) {          int[] data = new int[] { 1100, 192, 221, 12, 23 };          print(data);          radixSort(data, 10, 4);          System.out.println("排序后的數組：");          print(data);      }        public static void radixSort(int[] data, int radix, int d) {          // 緩存數組          int[] tmp = new int[data.length];          // buckets用于記錄待排序元素的信息          // buckets數組定義了max-min個桶          int[] buckets = new int[radix];            for (int i = 0, rate = 1; i < d; i++) {                // 重置count數組，開始統計下一個關鍵字              Arrays.fill(buckets, 0);              // 將data中的元素完全復制到tmp數組中              System.arraycopy(data, 0, tmp, 0, data.length);                // 計算每個待排序數據的子關鍵字              for (int j = 0; j < data.length; j++) {                  int subKey = (tmp[j] / rate) % radix;                  buckets[subKey]++;              }                for (int j = 1; j < radix; j++) {                  buckets[j] = buckets[j] + buckets[j - 1];              }                // 按子關鍵字對指定的數據進行排序              for (int m = data.length - 1; m >= 0; m--) {                  int subKey = (tmp[m] / rate) % radix;                  data[--buckets[subKey]] = tmp[m];              }              rate *= radix;          }        }        public static void print(int[] data) {          for (int i = 0; i < data.length; i++) {              System.out.print(data[i] + "/t");          }          System.out.println();      }    }  

　　運行結果：

1100    192    221    12    23    排序后的數組：12    23    192    221    1100    

轉自：http://blog.csdn.net/apei830/article/details/6596104