[[427990]]

この記事は、WeChat公式アカウント「JS日语問」（著者：慧慧）からの転載です。転載の許可については、「JS日语問」公式アカウントまでお問い合わせください。

I. それは何ですか?

挿入ソートは直接挿入ソートとも呼ばれ、少数の要素をソートするための効率的でシンプルなアルゴリズムです。

基本的な考え方は、特定の順序で順序付けられたテーブルにデータを 1 つずつ挿入し、最終的なシーケンスがソートされたデータになることです。

挿入ソートは、複数の人が手札を並べるのと同じような仕組みです。最初は左手は空で、テーブル上のカードは裏向きになっています。

次に、毎回テーブルからカードを 1 枚取り、左手の正しい位置に挿入します。そのためには、右から左へと、すでに手にある各カードと比較する必要があります。

たとえば、ソートされていない配列 3、1、7、5、2、4、9、6 を昇順でソートすると、次のようになります。

最初、順序付けられたテーブルは空だったので、3 が直接挿入されました。

2番目の数値から始めて、要素1を挿入し、それを順序付きリストのレコード3と比較します。1 < 3なので、レコード3の左側に挿入します。

レコード7を順序付きリストに挿入する際、順序付きリストのレコード3と比較されます。3 < 7なので、レコード3の右側に挿入されます。

レコード5を順序付きリストに挿入する場合、順序付きリストのレコード7と比較されます。5 < 7 かつ 5 > 3 なので、レコード5は3と7の間に挿入されます。

このパターンに従って、順序なしリストのレコード 4、9、および 6 が順序付きリストに順番に挿入されます。

II. これを達成する方法

最初のソートされていないシーケンスの最初の要素を順序付きシーケンスとして扱い、最後から 2 番目の要素をソートされていないシーケンスとして扱います。

ソートされていないシーケンスを最初から最後まで順番にスキャンし、スキャンされた各要素をソートされたシーケンス内の適切な位置に挿入します。

挿入する要素が順序付けられたシーケンス内の要素と等しい場合、挿入する要素は等しい要素の後に配置されます。

コード表現は次のとおりです。

関数挿入ソート(arr) {
 const len ​​= arr.length;
 preIndex、 current ;
 (i = 1; i < len; i++)の場合
プレインデックス = i - 1;
現在の= arr[i];
 while(preIndex >= 0 && arr[preIndex] > current ) {
 arr[preIndex+1] = arr[preIndex];
プレインデックス--;  
 }
 arr[preIndex+1] =現在の;
 }
 arrを返します。
 }

挿入ソートは、ソート対象の配列が既にソートされている場合に最適です。これは、現在の数値と前の数値を比較するだけで済むためです。この場合、合計N-1回の比較が必要となり、時間計算量はO(n)となります。

最悪のシナリオは、ソート対象の配列が逆順になっている場合です。この場合、必要な比較回数は最も多く、合計比較回数は1+2+3+…+N-1と表されます。したがって、挿入ソートの最悪ケースの時間計算量はO(n^2)となります。

上記から、挿入ソートは安定したソート方法であることがわかります。

III. アプリケーションシナリオ

挿入ソートの時間計算量は O(n²) であるため、データセットが小さく、アルゴリズムの安定性が求められる場合や、データが部分的または完全に順序付けられている場合のシーケンスのソートに適しています。

参考文献

• https://baike.baidu.com/item/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/7214992
• http://data.biancheng.net/view/65.html