一般的な基本的なソートアルゴリズムを今回から理解しましょう

[[383742]]

この記事はWeChatの公開アカウント「Beta Learns JAVA」から転載したもので、著者はSilently9527です。この記事を転載する場合は、Beta Learning JAVA パブリックアカウントにお問い合わせください。

この記事は Github リポジトリ https://github.com/silently9527/JavaCore に含まれています。

プログラマーがよく使用する IDEA プラグイン: https://github.com/silently9527/ToolsetIdeaPlugin

完全にオープンソースの Taobao プロジェクト: https://github.com/silently9527/mall-coupons-server

序文

すべてのプログラマーが最初に接触するアルゴリズムはソートアルゴリズムであると私は信じています。ソートはデータ処理と計算において重要な役割を果たしており、ソートアルゴリズムは他のアルゴリズムの基礎となることが多いためです。この記事では、基本的なソートアルゴリズムからアルゴリズムの学習を始めます。

ソートアルゴリズムのテンプレート

始める前に、ソートアルゴリズムの共通テンプレートを定義しましょう。以降のすべてのソートアルゴリズムはこのテンプレートを実装します。

パブリックインターフェースSortTemplate { 
 
    void sort(Comparable[] 配列); 
 
デフォルトvoid print(Comparable[]配列) {
 for (比較可能な a : 配列) {
            システム.out.print (a + " " );
        }
    } 
 
デフォルトのブール値 less(比較対象 a, 比較対象 b) {
 a.compareTo(b) < 0を返します。
    } 
 
デフォルトvoid exch(Comparable[] 配列、 int i、 int j) {
        比較可能なtmp = array[i];
        配列[i] = 配列[j];
        配列[j] = tmp;
    } 
     
 }

Comparable: 実装するソートアルゴリズムをより汎用的にし、任意のオブジェクトをソートするために、ここでは Comparable 配列を使用します。
ソート: ソートアルゴリズムはそれぞれ異なる方法で実装されるため、サブクラスで独自に実装します。
less: a < b の場合に true を返すパブリックメソッドが定義されています
exch: 配列内の2つのオブジェクトを交換するために定義されたパブリックメソッド
print: データ内の各要素を印刷する

選択ソート

アルゴリズム実装のアイデア：

まず配列内の最小の要素を見つけます。
実際には、配列の最初の要素と交換して、 1 つの要素が配置されるようにします。
残りの要素の中から最小の要素を再度見つけ、それを配列の 2 番目の要素と交換し、すべての要素が整列するまでこのプロセスを繰り返します。

コード実装:

パブリッククラスSelectionSortはSortTemplateを実装します。 
 
    @オーバーライド
パブリックvoid ソート(比較可能な[] 配列) {
 int長さ = 配列.長さ;
 ( int i = 0; i < 長さ; i++) {
整数 最小値= i;
 ( int j = i + 1; j < 長さ; j++) {
                if (less(配列[j], 配列[ min ])) {
最小値= j;
                }
            }
            exch(配列、i、 min );
        }
    } 
 
 }

入力配列がソートされている場合、選択ソートの実行にはソートされていない場合と同じくらいの時間がかかることがわかります。

N要素の配列の場合、選択ソートを使用する際の時間計算量はO(n2)である。

選択ソートは、移動するデータが最も少ないソートです。スワップの数は、配列のサイズに比例します。N 要素の配列には、N 回のスワップが必要です。

バブルソート

アルゴリズム実装のアイデア：

隣接する 2 つの要素を比較します。最初の要素が 2 番目の要素よりも大きい場合は、2 つの要素の位置を入れ替えます。

最後の要素まで、隣接する要素の各グループに対して同じ操作を実行します。操作が完了したら、最大の要素をランク付けできます。

配列内のすべての要素が整うまでこのプロセスを繰り返します。

コード実装:

パブリッククラスBubbleSortはSortTemplateを実装します。 
 
    @オーバーライド
パブリックvoid ソート(比較可能な[] 配列) {
 int長さ = 配列の長さ - 1;
 ( int i = 0; i < 長さ; i++) {
 ( int j = 0; j < 長さ - i; j++) {
                if (less(配列[j + 1], 配列[j])) {
                    exch(配列、j、j + 1);
                }
            }
        }
    } 
 
 }

N要素の配列の場合、バブルソートの時間計算量はO(n2)です。

挿入ソート

ポーカーをプレイしているとき、左側の分類されたカードの適切な位置に各カードを挿入してカードを並べることを想像してください。挿入ソートの考え方は似ている

アルゴリズム実装のアイデア：

最初の要素はデフォルトで最初に順序付けられ、現在のインデックスは 0 から始まります。
現在のインデックス位置を 1 つずつ移動します。現在のインデックス位置の左側の要素は順番になっています。コードを後ろから前に向かってスキャンし、現在のインデックス位置の要素と比較します。
現在のインデックス位置の要素が左側の順序付けられた位置に収まることを確認した後、その位置に挿入します。
現在のインデックス位置の要素がソートされた最後の要素より大きいと判断された場合、現在のインデックス位置は直接後方に移動します。
すべての要素が整うまでこのプロセスを繰り返します。

コード実装:

パブリッククラスInsertionSortはSortTemplateを実装します。 
 
    @オーバーライド
パブリックvoid ソート(比較可能な[] 配列) {
 int長さ = 配列.長さ;
 ( int i = 1; i < 長さ; i++) {
 for ( int j = i; j > 0 && less(array[j], array[j - 1]); j --) {  
                exch(配列、j、j - 1);
            }
        }
    } 
 
 }

コードの実装から、現在のインデックスの要素が左側の順序付き配列の最後の要素よりも大きい場合、内部ループが直接終了し、ソートする配列に部分的な順序があり、挿入ソートアルゴリズムが非常に高速になることがわかります。

最悪のケースを考えると、入力配列が反転されている場合、挿入ソートの効率は選択ソートと同じで、「時間計算量はO(n2)」です。

シェルソート

挿入ソートは、隣接する要素を交換するだけであり、要素は配列から正しい位置に少しずつしか移動できないため、大規模な順序不同の配列では遅くなります。挿入ソートは、部分的に順序付けられた配列をソートするのに非常に効率的です。

シェルソートは、これら 2 つの特性に基づいて挿入ソートを改良します。

アルゴリズム実装のアイデア

まず、サブ配列を分離するためのステップサイズ h を設定します。
挿入ソートを使用してhサブ配列を個別にソートする
hステップサイズを減らし、hステップサイズが1になるまでサブ配列のソートを続けます。
ステップサイズが 1 の場合、通常の挿入ソートになるため、配列は順序どおりに並んでいる必要があります。

シェルソートが効率的な理由は、ソートの開始時に各サブ配列が非常に短く、ソート後にサブ配列が部分的に順序付けられるためです。どちらの状況も挿入ソートに非常に適しています。

コード実装:

パブリッククラス ShellSort は SortTemplate を実装します { 
 
    @オーバーライド
パブリックvoid ソート(比較可能な[] 配列) {
ギャップ= 1;
 int長さ = 配列.長さ; 
 
        （ギャップ<長さ/3）{
            ギャップ = 3 * ギャップ + 1;
        } 
 
        ギャップ >= 1 の場合
( int i = ギャップ; i < 長さ; i++) {
 for ( int j = i; j >= gap && less(array[j], array[j - gap]); j -= gap) {
                    exch(配列、j、j - ギャップ);
                }
            }
            ギャップ = ギャップ / 3;
        }
    } 
 
 }