java桶式排序算法

/**


桶式排序:
*
僅支持非負數排序！
*
桶式排序不再是基于比較的了，它和基數排序同屬于分配類的排序， 這類排序的特點是事先要知道待排 序列的一些特征。 桶式排序事先要知道待排
序列在一個范圍內，而且這個范圍應該不是很大的。 比如知道待排序列在[0,M）內，那么可以分配M個桶，第I個桶記錄I的出現情況，
最后根據每個桶收到的位置信息把數據輸出成有序的形式。 這里我們用兩個臨時性數組，一個用于記錄位置信息，一個用于方便輸出數據成有序方式，
另外我們假設數據落在0到MAX,如果所給數據不是從0開始，你可以把每個數減去最小的數。
*/
public class BucketSort {
 public void sort(int[] keys, int from, int len, int max) {

 int[] temp = new int[len];
 int[] count = new int[max];

 for (int i = 0; i < len; i++) {
     count[keys[from + i]]++;
 }
 // calculate position info
 for (int i = 1; i < max; i++) {
     count[i] = count[i] + count[i - 1];// 這意味著有多少數目小于或等于i，因此它也是position+
                                         // 1
 }

 System.arraycopy(keys, from, temp, 0, len);
 for (int k = len - 1; k >= 0; k--)// 從最末到開頭保持穩定性
 {
     keys[--count[temp[k]]] = temp[k];// position +1 =count
 }

}
/**

@param args
*/
public static void main(String[] args) {
int[] a = { 1, 4, 8, 3, 2, 9, 5, 0, 7, 6, 9, 10, 9, 13, 14, 15, 11, 12,

     17, 16 };

BucketSort bucketSort = new BucketSort();
 bucketSort.sort(a, 0, a.length, 20);// 第四個參數為20，此參數必須比數組里最大值還要大，否則出錯
 for (int i = 0; i < a.length; i++) {

 System.out.print(a[i] + ",");

}
}




}</pre>