ソートアルゴリズム: 挿入ソートとシェルソート

今日は、挿入ソートとシェルソートという 2 つの古典的なソート方法について説明します。シェル ソートは、挿入ソートのアップグレード バージョンと考えることができます。

挿入ソート

挿入ソートのアルゴリズムの説明は、非常にシンプルで直感的なソート アルゴリズムです。その複雑さはバブルソートに似ています。動作原理は、並べ替えられていないデータの場合、並べ替えられたシーケンスの後ろから前に向かってスキャンして、対応する位置を見つけて挿入することです。

次のようなアニメーションをインターネットで見つけました。

プロセスは次のとおりです。

• ソートされたと考えられる最初の要素から開始します

• 次の要素を取り出します。要素を削除し、並べ替えた後、要素シーケンスを後ろから前にスキャンします

• 要素 (並べ替えられた) が新しい要素より大きい場合は、要素を次の位置に移動します

• までステップ 3 を繰り返します。新しい要素の位置以下のソートされた要素を見つけます

• この位置に新しい要素を挿入した後、ステップ 2 ～ 5 を繰り返します。

• コード実装（ここではC言語を使用しています）:

  void insort (int arr[], int len)
  {
      int i,current,preindex;
      for (i = 1; i < len; i++) {
          preindex = i - 1;
          current = arr[i];
          while (preindex >= 0 && current < arr[preindex]) {
              arr[preindex + 1] = arr[preindex];
              preindex --;
          }
          arr[preindex + 1] = current;
      }
  }

シェルソート

挿入ソートを理解すると、シェルソートを理解するのは簡単です。 シェル ソート アルゴリズムは、1959 年に D.L. シェルによって発明されました。その基本的な考え方は、最初に離れた要素を比較することで、多数の無秩序な状況を迅速に削減し、その後の作業を容易にすることができます。比較される要素間の距離は、1 まで減少するまで徐々に減少します。1 になった時点で、並べ替えは隣接する要素の交換になります。

ヒルソートは、テーブル内の特定の増分に従ってレコードをグループ化し、直接挿入ソートアルゴリズムを使用して各グループをソートします。増分が徐々に減少するにつれて、各グループにはさらに多くのキーワードが含まれます。ファイル全体が 1 つのグループに分割され、アルゴリズムが終了します。

プロセスのデモ (この写真もオンラインで見つかりました):

コードの実装 (ここでは C 言語が使用されています):

void shell_sort (int arr[], int len)
{
    int gap,i,current,preindex;
    for (gap = len / 2; gap > 0; gap /= 2) {
        for (i = gap; i < len; i++) {
            preindex = i - gap;
            current = arr[i];
            while (preindex >= 0 && current < arr[preindex]) {
                arr[preindex + gap] = arr[preindex];
                preindex -= gap;
            }
            arr[preindex + gap] = current;
        }
    }
}

以上がソートアルゴリズム: 挿入ソートとシェルソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。