bucket sort(桶排序)

假設輸入平均分布，也就是輸入的陣列每一種組合情況都是機率均等的，平均情況下他的時間複雜度為。和counting sort類似，都是對於輸入做出一些假設，才達到如此快的執行速度，counting sort假設陣列中的每一個元素都是界於1到n之間的整數，而bucket sort也同樣具有這項性質。

假設我們有個元素的陣列需要排序，每個元素都界於某一個數的區間，如到。

1. 建立桶子 : 建立個桶子，每一個桶子對應到某一個預期範圍的數字區間，如第一個桶子放置到的元素，第二個桶子放置到的元素，也就是假設元素在到之間，我們就在等分的劃分成個區域，將每個區域視為桶子，由於我們假設輸入平均分布，因此不大會出現所有元素都在同一個桶子的情況。
2. 放置元素 : 將陣列中的元素放到對應的桶子。
3. 排序 : 使用排序演算法對於每一個桶子中的元素進行排序。
4. 走訪 : 依序走訪每一個桶子中的元素，並且將元素放回原來的陣列，完成排序。

在bucket sort的程式碼中，我們假設輸入為包含個元素的陣列，每一個元素介於某一個數的區間，假設到，此外，我們還需要額外的空間，當作桶子來存放元素，陣列中存放的為鏈結串列(linked list)，方便我們進行走訪。

BUCKET-SORT(A)
n = A.length
let B[0...n-1] be a new array
for i = 0 to n - 1
    make B[i] an empty list
for i = 1 to n
    insert A[i] into list B[A[i]/10]
for i = 0 to n - 1
    sort list B[i] with insertion sort
concatenate the lists B[0],B[1],...,B[n - 1] together in order

以上面這個例子，就是將陣列中每一個元素依照其數字範圍，如0到10, 11到20依次放入桶子中，接著使用insertion sort對箱子內的元素進行排序，箱子皆為一個鏈結串列，將桶內元素串接再一起，接著從0號箱子開始走訪不是空的桶子，得到排序完成的陣列。

下面是C++實作

#include <iostream>
#include <vector>

using namespace std;
void bucket_sort(int *, int);
void insertion_sort(vector<int> &);
int main(void)
{
    int A[10] = {78, 17, 39, 26, 72, 94, 21, 12, 23, 68};
    bucket_sort(A, 10);
    for (auto i : A)
    {
        cout << i << ' ';
    }
}

void bucket_sort(int *A, int A_length)
{
    vector<int> B[10];
    for (int i = 0; i < A_length; i++)
    {
        int B_index = A[i] / 10;
        B[B_index].push_back(A[i]);
    }
    for (int i = 0; i < 10; i++)
    {
        insertion_sort(B[i]);
    }
    int A_index = 0;
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < B[i].size(); j++)
        {
            A[A_index++] = B[i][j];
        }
    }
}

void insertion_sort(vector<int> &B)
{
    for (int i = 1; i < B.size(); i++)
    {
        int key = B[i];
        int j = i - 1;
        while (j >= 0 && B[j] > key)
        {
            B[j + 1] = B[j];
            j--;
        }
        B[j + 1] = key;
    }
}

bucket sort效率

在虛擬碼中總共有3個for迴圈，迴圈主體中除了排序以外，最壞情況下時間複雜度皆為。假設我們使用的排序為插入排序，需要呼叫n次插入排序。

假設表示桶子中元素個數的隨機變數，插入排序在最差的情況下時間複雜度為，因此整個bucket sort在最差情況下的時間複雜度可以用下面的式子表示:

下面分析bucket sort在平均情況下的執行時間，也就是對輸入的數據取期望值，我們可以得到執行時間的期望值。

而這裡要先求出這一項，我們使用指示器隨機變數進行處理，對所有和，表示桶子的index, 表示陣列中元素的index，表示由桶子所組成的陣列，表示待排序的元素所在的陣列

這裡表示放入桶子的事件，發生表示1，反之為0。表示桶子中元素個數的隨機變數，因此這裡可以使用指示器隨機變數的和去表示元樹的隨機個數

接著為了計算，將平方項展開

指示器隨機變數，表示放入桶子的事件，發生的機率為，當此事件發生時，為1，因此

而在時，

將以上兩個式子代回

而我們上面得到的執行時間期望值為

將代換，得到

所以即使輸入的輸入不是均勻分布的，也就是數據不一定式平均分在散某一個區間，bucket sort還是能夠在線性時間內完成，只要符合以下性質

• 所有桶大小的平方和與陣列中元素的總數呈現線性關係

那麼bucket sort還是可以在線性時間內完成。

p.s: 感謝MuMu大大介紹displaystyle這個排版方式~~

參考資料:Introduciton to algorithms 3rd