/**
 * 桶式排序:
 *
 * 僅支持非負(fù)數(shù)排序！
 *
 * 桶式排序不再是基于比較的了，它和基數(shù)排序同屬于分配類(lèi)的排序， 這類(lèi)排序的特點(diǎn)是事先要知道待排 序列的一些特征。 桶式排序事先要知道待排
 * 序列在一個(gè)范圍內(nèi)，而且這個(gè)范圍應(yīng)該不是很大的。 比如知道待排序列在[0,M）內(nèi)，那么可以分配M個(gè)桶，第I個(gè)桶記錄I的出現(xiàn)情況，
 * 最后根據(jù)每個(gè)桶收到的位置信息把數(shù)據(jù)輸出成有序的形式。 這里我們用兩個(gè)臨時(shí)性數(shù)組，一個(gè)用于記錄位置信息，一個(gè)用于方便輸出數(shù)據(jù)成有序方式，
 * 另外我們假設(shè)數(shù)據(jù)落在0到MAX,如果所給數(shù)據(jù)不是從0開(kāi)始，你可以把每個(gè)數(shù)減去最小的數(shù)。
 */
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];// 這意味著有多少數(shù)目小于或等于i，因此它也是position+
                                                // 1
        }
 
        System.arraycopy(keys, from, temp, 0, len);
        for (int k = len - 1; k >= 0; k--)// 從最末到開(kāi)頭保持穩(wěn)定性
        {
            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);// 第四個(gè)參數(shù)為20，此參數(shù)必須比數(shù)組里最大值還要大，否則出錯(cuò)
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ",");
        }
 
    }
 
}

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。