2

我有一个vector<unsigned int> vec大小n。中的每个元素vec都在范围内[0, m]，没有重复，我要排序vec。如果允许您使用 O(m) 空间，是否有可能比 O(n log n) 时间做得更好？在平均情况下m比n在最坏情况下要大得多m == n。

理想情况下，我想要一些 O(n) 的东西。

我觉得有一种桶排序方式可以做到这一点：

  1. unsigned int aux[m];
  2. aux[vec[i]] = i;
  3. 以某种方式提取 permutation 和 permute vec。

我被困在如何做3。

在我的应用程序m中，大约是 16k。然而，这种类型是在内部循环中，占我运行时的很大一部分。

4

3 回答 3

3

基数排序，也不需要值小于 m 的限制。

下面的示例实现是在 int 类型上模板化的。如果您的 m 始终小于 2^15，则应尽可能使用 int16_t 向量（如果值始终为正，则应使用更好的 uint16_t 以避免处理有符号整数的偏移量）。对于 32 位整数，这将只需要两次排序，而不是 4 次。如果您无法更改输入类型，则可以将代码特殊情况下仅执行两次传递并避免带符号的偏移量。

这个实现是 O(n) 并且使用了 O(n) 额外空间（排序不到位）。

template<typename I>
void radix_sort(I first, I last) {
    using namespace std;
    typedef remove_reference_t<decltype(*first)> int_t;
    typedef make_unsigned<int_t>::type uint_t;

    const uint_t signedOffset = is_signed<int_t>::value ? uint_t(numeric_limits<int_t>::max()) + uint_t(1) : 0;
    auto getDigit = [=](uint_t n, int power) -> size_t { return ((n + signedOffset) >> (power * 8)) & 0xff; };

    array<size_t, 256> counts;
    vector<int_t> sorted(distance(first, last));
    for (int power = 0; power < sizeof(int_t); ++power) {
        counts.fill(0);
        for_each(first, last, [&](int_t i) { ++counts[getDigit(i, power)]; });
        partial_sum(begin(counts), end(counts), begin(counts));
        for_each(reverse_iterator<I>(last), reverse_iterator<I>(first), [&](int_t i) {
            sorted[--counts[getDigit(i, power)]] = i;
        });
        copy(begin(sorted), end(sorted), first);
    }
}
于 2013-10-30T03:08:55.333 回答
1

如果您知道 m = O(n 2 ) 的事实，则可以执行 base-n 基数排序来对数组进行排序。这就像一个普通的基数排序，但不是有 2 个桶或 10 个桶，而是有 n 个桶，每个可能的基数为 n 位的数字一个。

由于以 b 为底的基数排序的运行时间是 O(n log b U)，其中 U 是最大值，在这种情况下，我们知道运行时间是 O(n log n n 2 ) = O(n)。这比 O(n log n) 渐近地快。它也只需要 O(n) 内存，低于 O(m) 的限制。

希望这可以帮助！

于 2013-10-30T03:16:23.940 回答
0

不，你需要这样做：

unsigned int aux[m + 1];
bzero(aux, sizeof(aux));

foreach x in (vec) { aux[x]++; }

for(x = 0; x <= m; x++)
  for(qty = 0; qty < x; qty++)
    output(x);
于 2013-10-30T03:10:29.217 回答