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. どういうわけか順列と順列を抽出しvecます。

3のやり方で困っています。

私のアプリケーションmでは、16k 程度です。ただし、この並べ替えは内側のループにあり、ランタイムのかなりの部分を占めています。

4

3 に答える 3

3

基数ソートでは、値が m 未満であるという制限も必要ありません。

以下の実装例は、int 型でテンプレート化されています。m が常に 2^15 未満である場合は、可能であれば int16_t のベクトルを使用する必要があります (符号付き整数を処理するためのオフセットを回避するために、値が常に正の場合は uint16_t を使用することをお勧めします)。これにより、32 ビット整数の場合は 4 つではなく、2 つのソート パスのみが必要になります。入力タイプを変更できない場合は、コードを特別なケースにして、2 つのパスのみを実行し、符号付きオフセットを回避できます。

この実装は 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 ) であることがわかっている場合は、基数 n 基数の並べ替えを実行して配列を並べ替えることができます。これは通常の基数ソートに似ていますが、2 個のバケットまたは 10 個のバケットを使用する代わりに、数値の基数 n の数字ごとに 1 つずつ、n 個のバケットを使用します。

基数 b の基数ソートの実行時間は O(n log b U) (U は最大値) であるため、この場合、実行時間は O(n log n n 2 ) = O(n)であることがわかります。これは、O(n log n) よりも漸近的に高速です。また、O(m) の制限を下回る O(n) メモリしか必要としません。

お役に立てれば！

于 2013-10-30T03:16:23.940 に答える