Javaソートアルゴリズムの概要（I）：挿入ソート

挿入ソートの基本的な操作は、ソートされた順序付けられたデータにデータを挿入し、それによって番号が 1 つ増加した新しい順序付けられたデータを取得することです。比較と交換の時間計算量は O(n^2) です。アルゴリズムは適応型です。データが基本的に順序付けられている場合、時間計算量は O(n) です。アルゴリズムは安定しており、オーバーヘッドが低くなっています。このアルゴリズムは、データが基本的に順序付けられている場合や、データの量が少ない場合に適しています。

挿入アルゴリズムは、ソートする配列を 2 つの部分に分割します。最初の部分には配列の最初の要素を除くすべての要素が含まれ、2 番目の部分にはこの 1 つの要素のみが含まれます。 *** 部分がソートされたら、ソートされた *** 部分の位置に *** 要素を挿入します。

アルゴリズムの説明

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

1. 最初の要素から始めて、要素はソートされているとみなすことができます

2. 次の要素を取り出し、ソートされた要素の順序で後ろから前へスキャンします。

3. 要素（すでにソートされている）が新しい要素より大きい場合は、要素を次の位置に移動する

4. ソートされた要素が新しい要素より小さいか等しい位置が見つかるまで、手順3を繰り返します。

5. 新しい要素を次の位置に挿入する

6. 手順2を繰り返します

比較演算のコストが交換演算のコストよりも大きい場合は、バイナリ検索を使用して比較演算の数を減らすことができます。このアルゴリズムは、バイナリ検索ソートと呼ばれる挿入ソートのバリエーションと考えることができます。

コードの実装

公共  void insertionSort() { // 挿入ソート 
 intアウト、イン;
 int count1 = 0 , count2 = 0 ; // コピー数、比較回数 
 (out = 1 ; out < nElems; out++)の場合{
長いtemp = a[out];
イン = アウト;
ブール値flag=in> 0 &&a[in- 1 ]>=temp;
 while (フラグ){
 (a[in- 1 ]>=temp)の場合{
 （ 0以上）の場合
a[in]=a[in- 1 ];
カウント1++;
 - で;
 }
 }
カウント2++;
フラグ=in> 0 &&a[in- 1 ]>=temp;
 }
 a[in] = 温度;
 }
 System.out.println( "コピー数: " + count1 + "比較数: " + count2);
 }

データがすでに特定の順序になっている場合、挿入ソートの方が効率的です。しかし、データが不規則な場合は大量のデータを移動する必要があり、その効率はバブルソートや選択ソートと同じくらい悪くなります。

【編集者のおすすめ】

1. 18.1.4 挿入ソート
2. C# 直接挿入ソートの紹介
3. C++ ソートに関する 4 つの古典的な講義: 挿入ソート