0

我正在尝试在 C++ 中创建一个桶排序算法，但它根本不起作用。每次运行时，它都会将许多新数字添加到数组中，这些数字通常非常大，例如数十亿。有人知道为什么是这样吗？这是代码 - （请注意，我传入一个大小为 100 的数组，随机数从 0 到 ~37000，并且插入排序功能功能齐全并经过多次测试）

如果有人能指出问题所在，将不胜感激。

void bucketSort(int* n, int k) 
{
    int c = int(floor(k/10)), s = *n, l = *n;
    for(int i = 0; i < k; i++) {
        if(s > *(n + i)) s = *(n + i);
        else if(l < *(n + i)) l = *(n + i);
    }
    int bucket[c][k + 1];
    for(int i = 0; i < c; i++) {
        bucket[i][k] = 0;
    }

    for(int i = 0; i < k; i++) {
        for(int j = 0; j < c; j++) {
            if(*(n + i) >= (l - s)*j/c) {
                continue;
            } else {
                bucket[j][bucket[j][k]++] = *(n + i);
                break;
            }
        }
    }

    for(int i = 0; i < c; i++) {
        insertionSort(&bucket[i][0], k);
    }
}
4

1 回答 1

0

此行不编译。int bucket[c][k + 1];

我认为问题出在您的存储桶索引上。这部分在这里

for(int j = 0; j < c; j++) {
   if(*(n + i) >= (l - s)*j/c) {
        continue;
   } else {
        bucket[j][bucket[j][k]++] = *(n + i);
        break;
   }
}

不等同于：

  insert n[i] into bucket[ bucketIndexFor( n[i]) ]

首先，它将索引减一。因此，它也错过了最后一个桶的数字的中断。还引入了一个小错误，因为索引计算使用的是 range[0,l-s]而不是，只有当equals[s,l]时才相同。s0

当我写成bucketIndex：

int bucketIndex( int n, int c, int s, int l )
{
    for(int j = 1; j <= c; j++) {
        if(n > s + (l-s)*j/c) {
            continue;
        } else {
            return j-1;
        }
    }
    return c-1;
}

并将算法的主要部分重写为：

std::vector< std::vector<int> > bucket( c );

for(int i = 0; i < k; i++) {
    bucket[ bucketIndex( n[i], c, s, l ) ].push_back( n[i] );
}

我将物品正确插入他们的桶中。

于 2013-02-16T19:54:03.010 回答