-1

几个小时以来，我一直试图理解这段代码，但没有成功。我编写了自己的珠子排序算法版本，但是速度太慢了。我想了解为什么这个工作得这么快。这里是关于珠排序算法的信息：
http
://demonstrations.wolfram.com/ExtendedBeadSort/ 你能帮我理解这个算法是如何工作的吗？

#include <iostream>
#include <vector>

using std::cout;
using std::vector;

void distribute(int dist, vector<int> &List) {
    //*beads* go down into different buckets using gravity (addition).
    if (dist > List.size() )
        List.resize(dist); //resize if too big for current vector

    for (int i=0; i < dist; i++)
        List[i]++;
}

vector<int> beadSort(int *myints, int n) {
    vector<int> list, list2, fifth (myints, myints + n);
    cout << "sakums\n";
    cout << myints<< "\n";
 //   for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it) cout << " " << *it << "\n";
    cout << "beigas\n";

    cout << "#1 Beads falling down: ";
    for (int i=0; i < fifth.size(); i++)
        distribute (fifth[i], list);
    cout << '\n';

    cout << "\nBeads on their sides: ";
    for (int i=0; i < list.size(); i++)
        cout << " " << list[i];
    cout << '\n';

    //second part

    cout << "#2 Beads right side up: ";
    for (int i=0; i < list.size(); i++)
        distribute (list[i], list2);
    cout << '\n';

    return list2;
}

int main() {
    int myints[] = {734,3,1,24,324,324,32,432,42,3,4,1,1};
    vector<int> sorted = beadSort(myints, sizeof(myints)/sizeof(int));
    cout << "Sorted list/array";
    for(unsigned int i=0; i<sorted.size(); i++)
        cout << sorted[i] << ' ';
    system("PAUSE");
    return 0;
}
4

2 回答 2

1

它是我的实现！我是您在 Rosettacode 上看到的 C++ 中的珠子排序的原作者。

算法这么慢的原因是因为这种排序存在三个主要的减速问题。一个处理每次分发运行 O(S) 时向量的潜在调整大小。这也与每个“极点” O(S)+O(S) 或 O(2S) 的实际数字一一相加相结合，然后执行 n 次，其中 n 是要排序的数字 O(n )+O(2S)。由于在大多数情况下 S 仍然较大，因此该算法仍然是 O(S)。

公平地说，只需要有人对我的代码进行更好的实现和不那么冗长的版本来提高性能。我以这种方式制作了这个算法，以便尽可能容易地向刚接触珠子排序的人展示。

如果您想了解更多信息，请查看 wiki page of bead sort。

于 2013-05-02T20:03:06.377 回答
0

由于分发的工作方式：

其他每个数字都为插槽贡献“珠子” - 有 13 个数字，因此插槽 1 完成第一遍时其中有 13 个。

它在“列”中“分配”珠子，即当您在其侧面打印时，现在有 734 个插槽 - 数量最多。

当再次运行分发时，它通过对列求和来将“珠子”向下移动 - 它将根据最大元素执行一些加法 * 数字的数量 - 加上内存分配

于 2012-12-04T23:21:32.660 回答