c++ - 何时有效使用桶排序以及需要多少个桶？

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 来创建二维 vector (而不是 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 万的测试