BucketSort（桶排序）原理及C++代码实现

桶排序假设输入数据服从均匀分布，平均情况下它的时间复杂度为O（n）。

桶排序将输入数据的区间均匀分成若干份，每一份称作“桶”。分别对每一个桶的内容进行排序，再按桶的顺序输出则完成排序。

通常使用链表来实现桶。

代码如下：（仅供参考）

void Insert(vector<double> & bkt, double num) {

    for (vector<double>::iterator p = bkt.begin(); p != bkt.end(); ++p)

        if (*p > num) {

            bkt.insert(p, num);

            return ;

        }

    bkt.push_back(num); //没有找到，就放最后

}

void BucketSort(double * const begin, double * const end) {  //假设输入数据都是小数[0,1)

    int n = end - begin;

    int i;

    vector<vector<double>*> bucket(n); //为什么是n个桶，应该和hash一个原理

    for (i = ; i < n; ++i)

        bucket[i] = new vector<double>;

    for (i = ; i < n; ++i) { //按顺序插入到桶中

        Insert(*bucket[static_cast<int>(*(begin + i) * n)], *(begin + i));

    }

    int j = , k = ;

    for (i = ; i < n; ++i) {

        while (k >= bucket[j]->size()) { //如果出现连续的空桶

            ++j;

            k = ;

        }

        *(begin + i) = (*bucket[j])[k++];

    }

    for (i = ; i < n; ++i)

        delete bucket[i];

}