3

最大値まで昇順で、次に降順で番号が付けられている要素を持つ配列があるとします。

Eg. int a[] = { 10, 12, 14, 16, 15, 13, 11}.

この配列を効率的にソートするにはどうすればよいですか？

配列はインプレースでソートする必要があります。

4

3 に答える 3

8

最大値を見つけて、その値まで配列を逆にします。次に、2つのサブ配列にマージを適用します。最初のサブ配列には最大値が含まれ、残りの配列よりも多くなります。これには線形の計算の複雑さがあり、線形の追加メモリが必要になります。

あなたの場合：

a[] = { 10, 12, 14, 16, 15, 13, 11}=>{10,12,14,16}, {15,13,11}

=>リバース（線形、インプレース）=>

{16,14,12,10}, {15,13,11}

=> merge（linear、additional linear memory）=>

{16,15,14,13,12,11,10}

編集：追加のメモリなしで2つのアレイを所定の位置にマージする方法については、この回答を参照してください

于 2013-01-23T13:38:11.303 に答える
6

私の解決策：

  1. 配列の開始と配列の終了の2つのポインターを取ります。

  2. 結果の配列に、両方のポインターから最小値（または降順でソートする必要がある場合は最大値）を書き込み、ポインターを1つの位置（開始ポインター+1の位置と終了ポインター-1の位置）にシフトします。

  3. 開始ポインタが終了ポインタの後に配置されるまで繰り返します。

解の複雑さはO（N）です。必要なメモリはO（N）です

擬似コード：

function Sort(a)
{
  startPointer = 0;
  endPointer = a.length-1;
  result = new Array of size a.length
  while (startPointer <= endPointer)
  {
    var newValue;
    if (a[startPointer] < a[endPointer])
    {
      newValue = a[startPointer];
      startPointer +1
    }
    else
    {
      newValue = a[endPointer];
      endPointer -1
    }
    result[a.length - startPointer - endPointer] = newValue;
  }

  return result;
}

更新された質問の解決策：

解決策として、配列の最初の部分の部分的なソートを使用します。

（10および11）上のポインタ{10、12、14、16、15、13、11}

（12と11）のポインタースワップ12と11 {10、11、14、16、15、13、12}

（14と12）のポインタ14と12を入れ替えます{10、11、12、16、15、13、14}//ポインタを14から13に移動します。

これで、{10、11、12}とサブ問題を{16、15、13、14}に並べ替えました（サブ問題のNは2倍に減少しました）

このアルゴリズムの複雑さは次のとおりです。O（N）+（N / 2）+ O（N / 4）+ ...完全にO（N）

より良い説明のための画像：

ここに画像の説明を入力してください

于 2013-01-23T13:45:07.617 に答える
2

質問のプロパティを使用します。

すでにソートされている配列をソートする必要はありません。変更が行われるポイントを見つけてからslope、適切なものを使用しalgorithmて完全にソートされた配列を取得します。

このプロパティを効率的に使用するバイトニックソートの実装を検討できます。

于 2013-01-23T13:57:32.420 に答える