2

固定長配列を使用して循環バッファーを実装しました。有効なデータの開始点を示すために、インデックス ( _startIndex) を使用します。同様に、有効なデータの末尾を指すために、別のインデックス ( _endIndex) を使用します。以下は例です。

  9   8   7   6   5   4   3   2   1   0   <-- array indices
  3   2   1   0                   5   4   <-- buffer indices
-----------------------------------------
|   |   |   |   |   |   |   |   |   |   |
-----------------------------------------
              ^                   ^
             _startIndex         _endIndex

次に、このバッファーの要素を再配置する必要があります。最小の要素をバッファーの位置 0 に移動し、最大の要素をバッファーの位置 5 に移動する必要があります。

私の考えは、次の方法に基づいています。

int GetArrayIndex(int bufferIndex)
{
    return (_startIndex + bufferIndex) % LENGTH;
    // LENGTH is the length of the array
}

このように、ソート アルゴリズムは、上記の方法を使用してバッファを順番に読み取ることができるため、バッファが同じ配列の 2 つの連続しない部分で構成されていることを意識する必要はありません。循環バッファをソートするより良い方法はありますか?

4

3 に答える 3

7

インプレース ソートを実行する場合は、最初にバッファを圧縮する必要があります。つまり、インデックス 0 からインデックス 5 までの 1 つの連続したブロックにします。

次に、Array.Sort(T[], index, length)オーバーロードを呼び出して、配列のその部分を並べ替えることができます。

何をどこに移動するかさえ分かれば、ワンタッチでアイテムを移動できます。

次の 3 つのケースがあります。

  1. start_index == 0：移動不要

  2. start_index < end_index: 移動するアイテムの数は です(end_index - start_index + 1)。アイテムを位置 '0' から 'count-1' まで移動start_indexしend_indexます

  3. start_index > end_index: 配列に「穴」があります (表示したように)。start_indexアイテムを配列の最後から positionに移動する必要がありますarray.length - start_index - count。

ソースと宛先の位置を把握したら、Buffer.BlockCopyを呼び出してアイテムを移動できます。

start_index移動と並べ替えが完了したら、0 と にend_index設定できることに注意してくださいcount-1。または、バッファーを以前と同じ状態にしたい場合 (アイテムの並べ替えのみ)、上で説明したのと同じ種類のロジックを使用して元に戻すことができます。なぜそれをしたいのかは不明です。

于 2013-05-15T19:48:25.340 に答える
1

簡単な解決策:

  1. 値が位置 0、1、...、M-1 を占めるように要素を移動します。ここで、M は配列内で使用される位置の数です。
  2. _startIndex = 0 および _endIndex = M-1 を変更します。
  3. 0 から _endIndex までのバッファーの部分で Array.Sort を呼び出します。

このソリューションは、O(M) ステップで要素を並べ替え、O(MlogM) で並べ替えを実行し、合計 O(MlogM) 時間かかります。言い換えれば、要素をバッファの先頭に再配置するのに必要な時間は、それらを並べ替えるのに必要な時間と比較してごくわずかです。

別の解決策は、バッファーの最初と 2 番目の部分を別々に並べ替えてから、それらを配列の先頭にマージして並べ替えることです。実行時間は同じで (正確には少し長くなります)、コードはより複雑です。

于 2013-05-15T19:53:11.077 に答える
1

変更されたクイックソートの実装を提案します。

クイックソートは「分割統治」アルゴリズムであり、セットを 2 つに分割してから続行することを意味します。バッファはすでに 2 つの部分に分割されているため、調整する必要があります。最初のステップは、2 つの部分を並べ替えることです。最初の部分は配列の先頭にあり、2 番目の部分は配列の最後にあります。2番目の部分のすべての要素が最初の部分のどの部分よりも小さくなるように、要素を「事前に並べ替える」だけです。次に、クイックソートアルゴリズムをすべてのピースに適用すると、ソートされます

于 2013-05-15T19:53:53.433 に答える