何时有效地使用存储桶排序，需要多少个存储桶？

Question

你好，我想实现一个存储桶排序。我想这对我很有效：

#include <iostream>
using namespace std;
#include <vector>
#include <cmath>
#include <algorithm>


void bucket_sort(int[], const int);

int main(){
    system("color 1f");

    int array[] = {
        5, 77, 99, 100, 77, 57, 23, 1, 2, 57,
            81, 24, 21
    };

    cout << "before sorting: " << endl;
    for(auto x : array)
        cout << x << ", ";
    cout << endl;

    bucket_sort(array, 13);

    cout << "after sorting: " << endl;
    for( auto x : array)
        cout << x << ", ";

    cout << endl << endl;
    return 0;
}

void bucket_sort(int array[], const int size){
    int bucket = 10, divider;
    int min = array[0], max = array[0], j;

    for(auto i(0); i != size; ++i){
        if(min > array[i])
            min = array[i];
        if(max < array[i])
            max = array[i];
    }

    divider = (ceil( (double)(max + 1) / bucket) );
    std::vector<int>* vi = new vector<int>[bucket];

    for(i = 0; i < size; i++){
        j = floor(array[i] / divider);
        vi[j].push_back(array[i]);
    }

    for(i = 0; i < bucket; i++)
        std::sort(vi[i].begin(), vi[i].end());

    int k = 0;
    for(i = 0; i < bucket; i++){
        for(int j(0); j < vi[i].size(); j++){
            array[k] = vi[i][j];
            k++;
        }
    }

    delete[]vi;
}

代码运行得很好。但这是我应该做的吗？如果我有一个数组，它们的值很接近，但是有一两个值太大了：

66, 42, 70, 10, 30, 32, 28, 1000, 50000

如何应用这种存储桶排序算法？另外，我应该使用多少个桶？

Answer 1

我不确定你是从哪里得到数字10的。你可以使用数组中项目的总数。

您可以声明vector的vector来创建2-D向量(而不是new)

vector<vector<int>> vec;

理想情况下，bucket_sort不应该依赖其他排序方法。这是一个使用递归的版本。它不断迭代，直到每个存储桶中有零个或一个元素(或具有相同值的多个元素)。

示例：

void bucket_sort(std::vector<int> &src)
{
    if(src.size() <= 1)
        return;

    int min = *std::min_element(src.begin(), src.end());
    int max = *std::max_element(src.begin(), src.end());
    if(min == max)
        return;

    std::vector<std::vector<int>> vec;
    vec.resize(src.size());

    for(int i = 0; i < src.size(); i++)
    {
        //edit: double precision required 
        int v = int(double(src[i] - min) * src.size() / double(max - min + 1));
        vec[v].push_back(src[i]);
    }

    for(size_t i = 0; i < vec.size(); i++)
        //std::sort(vec[i].begin(), vec[i].end());
        bucket_sort(vec[i]);

    int index = 0;
    for(size_t i = 0; i < vec.size(); i++)
        for(size_t j = 0; j < vec[i].size(); j++)
            src[index++] = vec[i][j];
}

int main()
{
    std::vector<int> src = {66, 66, 42, 70, 10, 30, 32, 28, 1000, 50000 };
    for(auto x : src) cout << x << ", ";
    cout << endl;
    bucket_sort(src);
    for(auto x : src) cout << x << ", ";
    cout << endl << endl;
    return 0;
}

测试：

int test()
{
    srand((unsigned int)time(NULL));

    //add 1 million random numbers for testing
    std::vector<int> src;
    for(int i = 0; i < 1000000; i++)
        src.push_back(rand());
    bucket_sort(src);

    for(size_t i = 1; i < src.size(); i++)
        if(src[i - 1] > src[i])
        {
            cout << "fail\n";
            return 0;
        }
    cout << "success\n";

    return 0;
}

编辑:将除法计算改为double精度，增加了100万的测试