Day-15 线性时间演算法 : Bucket sort

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