JavaScript は古典的な並べ替えアルゴリズムの挿入ソートを実装します

挿入ソートのコード実装はバブル ソートや選択ソートほど単純で粗雑ではありませんが、ポーカーをプレイしたことがある人なら誰でも数秒で理解できるはずなので、その原理は最も理解しやすいはずです。ポーカーの手を並べ替えるのと同じように、左手を空にし、テーブル上のカードを下向きにして開始します。次に、毎回テーブルからカードを 1 枚取り出し、左手の正しい位置に挿入します。カードの正しい位置を見つけるために、左手にあるすべてのカードと右から左に比較します。元々はテーブルの山の一番上のカードでした。

1) アルゴリズム原理

挿入ソート (Insertion-Sort) のアルゴリズムの説明は、シンプルで直感的なソート アルゴリズムです。これは、順序付けされたシーケンスを構築することによって機能します。ソートされていないデータの場合は、ソートされたシーケンス内で後ろから前にスキャンして、対応する位置を見つけて挿入します。挿入ソートの実装では、通常、インプレース ソートが使用されます (つまり、O(1) 個の余分なスペースのみを使用するソート)。したがって、後ろから前へのスキャン プロセス中に、ソートされた要素を繰り返して徐々に行う必要があります。後方にシフトされ、最新の要素の挿入スペースが提供されます。

2) アルゴリズムの説明と実装

一般的に、挿入ソートはインプレースを使用して配列に実装されます。具体的なアルゴリズムは次のように説明されます。

要素はソート済みであると見なされます。

ソート済みの要素を後ろから前にスキャンします。要素シーケンス;

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

並べ替えられた要素が小さい位置が見つかるまで手順 3 を繰り返します。新しい要素と等しいか

この位置に新しい要素を挿入した後、手順 2 ～ 5 を繰り返します。

3) JavaScript コードの実装

function insertSort(arr) { 
    for (var i = 1; i < arr.length; i++) { 
      var temp = arr[i]; 
      var j = i - 1; 
      while (j >= 0 && arr[j] > temp) { 
        arr[j + 1] = arr[j]; 
         j--; 
      } 
      arr[j + 1] = temp; 
    } 
    return arr; 
 } 
var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; 
console.log(insertSort(arr));

挿入ソートの改善: 挿入位置を見つけるときに二分検索を使用します。 steps：多数の位置。 T(n) = O(n)

最悪の場合: 入力配列は降順でソートされます。 T(n) = O(n2)

平均的な状況: T(n) = O(n2)

以上がこの記事の全内容であり、皆さんの学習に役立つことを願っています。 PHP 中国語 Web サイトをサポートします。

古典的な並べ替えアルゴリズムを実装するための JavaScript を使用した挿入並べ替えに関連するその他の記事については、PHP 中国語 Web サイトに注目してください。