簡單桶排序（Bucket Sort）-有解無憂

1.基本思想

桶排序是將待排序集合中處于同一個值域的元素存放在同一個桶中¹，

2.演算法設計²

假設有一個班級有5個人，這次期末他們分別考了5分，2分，4分，5分，8分（滿分為10分），需要將這些分數從小到大排序

首先我們申請一個大小為11的陣列int bucket[11]，在最開始的時候我們都把該陣列的元素bucket[0]~bucket[10]都初始化為0，表示這些分數都還沒有人得到過，例如bucket[0]表示的是目前還沒有人得到0分，bucket[8]表示的是目前還沒有人得到8分，

開始處理每一個分數，第一個人的分數為5分，那么就將bucket[5]的值在原來的基礎上加1，即bucket[5]的值從0變為1，表示5分出現過一次
第二個人的分數為2分，那么就將bucket[2]的值在原來的基礎上加1，即bucket[2]的值從0變為1，表示2分出現過一次
第三個人的分數為4分，以此類推，可得
第四個人的分數為5分，注意了，我們在bucket[5]的值在原來的基礎上加1，那么bucket[5]的值從1變為2，表示5分出現兩次
最后一個人的分數為8分，得

最終，只需要將出現過的分數列印出來

3.代碼

public class SimpleBucketSort {
    public static void main(String[] args) {
        // 下面是學生取得的分數，假設分數最大為10
        int[] a = {5,3,5,2,8};
        // 創建11個分數層，a[0]=0:表示分數為0分的出現0個人
        int[] bucket = new int[11];
        for(int i = 0; i < a.length; i++) {
            // 出現分數為a[i]的有barrel[a[i]]個人
            bucket[a[i]]++;
        }
        // 列印
        for (int i = 0; i < bucket.length; i++) {
            // 出現幾次就列印幾次
            for(int j = 1; j <= bucket[i]; j++) {
                System.out.print(i + " ");
            }
        }
    }
}

4.復雜度

時間復雜度

在初始化桶時，需要回圈n次（n為桶的個數，在java語言中默認都已經初始化為0），在把分數放入桶中時，回圈了m次（m為待排序的個數），而在列印時一共回圈了（m+n）次，所以整個排序演算法一共執行了（n+m+m+n）次，用大寫的O來表示時間復雜度，因此該演算法的時間復雜度為O(n+m+m+n)，即O(2(n+m))，但是一般在說時間復雜度時都是忽略常數，也就是桶排序的最終時間復雜度為O(m+n)，并且一般字母都得大寫表示，即O(M+N)，

空間復雜度

桶排序所占用的空間比較糟糕，非常浪費空間，如果要排序的數的范圍在0~10000000000000，那得創建出10000000000001個變數，創建N個桶，并且待排序的數為M，那么空間復雜度為O(N+M)，

5.優缺點

優點

速度是比較快的，從上面的時間復雜度可以看出，

缺點

比較浪費空間，假設待排序的數中有一個元素值為2100000000000，那么必須創建一個大于2100000000000的桶數，

6.思考

該演算法其實可以來做去重復元素，只需要在列印時做一點改動，

// 列印（去重）
for(int i = 0; i < barrel.length; i++) {
    if(barrel[i] != 0) {
        // 列印的是分數
        System.out.print(i + " ");
    }
}

目前使用桶排序來對分數進行排序，那么目前要是姓名和分數，要求將名字按分數從小到大排序后列印輸出，目前的簡單桶排序做不到，輸出的只能是分數，

參考博客：https://www.jianshu.com/p/204ed43aec0c ??
參考書籍：《啊哈！演算法》 ??

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/110928.html

標籤：其他

上一篇：PAT乙級1007

下一篇：堆疊