10の古典的なソートアルゴリズム

[[432257]]

ソースコードはこちら GitHub: https://github.com/nateshao/leetcode

頑固なアルゴリズムシリーズ

面接では、基本的に最初にアルゴリズムについて質問します。特に大企業では、アルゴリズムに対する要件が非常に高くなります。

プログラマーの場合、アルゴリズムが得意な人は特に早くコードを書くことができます（私たちのクラスにもそういう生徒が何人かいます）。そして、問題に遭遇したとき、彼は多くの解決策を考えることができます。

もちろん、アルゴリズムを学ぶことは比較的退屈なことです。しかし、アルゴリズムの考え方を理解すると、アルゴリズムは本当に魔法のようなもので、アルゴリズムから導き出された考え方は非常に重要であることがわかります。そのため、Qianyuはアルゴリズムに関する一連の記事を引き続き研究し、皆さんと一緒に学び、向上していきます。この記事では主に、上位 10 個の古典的なソートアルゴリズムについて説明します。さあ、始めましょう！

時間計算量の理解

定数時間演算: 演算がデータ量に関係せず、毎回一定時間内に完了する場合、定数演算と呼ばれます。時間の複雑さは、アルゴリズムプロセスにおける定数操作の数を示す指標です。多くの場合、O (ビッグオーと発音) で表現されます。具体的には、演算数が定数の式では、高次の項のみが必要で、低次の項や高次の項の係数は必要ありません。残りの部分を f(N) として記録すると、時間計算量は O(f(N)) になります。

アルゴリズムプロセスの品質を評価するには、まず時間複雑度インジケーターを確認し、次にさまざまなデータサンプルでの実際の実行時間、つまり定数時間を分析します。

古典的なソートアルゴリズムのトップ10

アルゴリズム	時間計算量（平均）	時間計算量（最悪の場合）	時間計算量（最適）	空間の複雑さ	安定性
バブルソート	（n2）	（n2）	の上）	オー(1)	安定させる
選択ソート	（n2）	（n2）	（n2）	オー(1)	不安定
挿入ソート	（n2）	（n2）	の上）	オー(1)	安定させる
シェルソート	O(n1.3)	（n2）	の上）	オー(1)	不安定
クイックソート	O(nlog2n)	（n2）	O(nlog2n)	O(nlog2n)	不安定
マージソート	O(nlog2n)	O(nlog2n)	O(nlog2n)	の上）	安定させる
カウントソート	O(n+k)	O(n+k)	O(n+k)	O(n+k)	安定させる
基数ソート	O(n*k)	O(n*k)	O(n*k)	O(n+k)	安定させる
バケットソート	（n2）	O(n*k)	の上）	O(n+k)	安定させる
ヒープソート	O(nlog2n)	O(nlog2n)	O(nlog2n)	オー(1)	安定させる

ソートの定義

キーに従ってオブジェクトのシーケンスをソートします。

用語

安定: a が元々 b の前にあり、a=b の場合、ソート後も a は b の前にあります。
不安定: a が元々 b の前にあり、a=b の場合、ソート後に a が b の後に表示されることがあります。
内部ソート: すべてのソート操作はメモリ内で実行されます。
外部ソート: データが大きすぎるため、データはディスク上に配置され、ディスクとメモリ間のデータ転送を通じてソートが実行されます。
時間の複雑さ: アルゴリズムの実行にかかる時間。
空間計算量: プログラムを実行するために必要なメモリの量。

1. バブルソート

時間計算量、追加の空間計算量

バブルソートは、バブルソートとも呼ばれ、単純なソートアルゴリズムです。ソートする配列を繰り返し処理し、一度に 2 つの要素を比較して、順序が間違っている場合はそれらを交換します。シーケンスを訪問する作業は、交換が不要になるまで、つまりシーケンスがソートされるまで繰り返されます。このアルゴリズムの名前は、小さな要素が交換を通じてゆっくりとシーケンスの先頭に「浮かんで」いくという事実に由来しています。

アイデア:

隣接する要素を比較します。最初のものが 2 番目のものより大きい場合は、それらを交換します。

隣接する要素の各ペアに対して同じ操作を実行します。最初は最初のペアから始めて、最後は最後のペアで終了します。このステップが完了すると、最後の要素が最大の数値になります。

最後の要素を除くすべての要素に対して上記の手順を繰り返します。

コード実装:

パッケージ com.nateshao.basic_01_ten_sort; 
 
 /**
 * @日付Shao Tongjieによって2021/10/29 16:52に作成
 * @WeChatパブリックアカウントプログラマーQianyu
 * 個人ウェブサイト www.nateshao.cn
 * @ブログ https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * 説明: 元のリンク https://zfhelo.gitee.io/2020/06/14/1/
 */
パブリッククラス Code_01_BubbleSortTest {
公共 静的void main(String[] args) {
 int [] arr = {3、44、38、5、47、15、36、26、27、2、46、4、19、50、48};
        バブルソート(arr);
        System.out.println (Arrays.toString(arr)) ;
    }
公共 静的voidバブルソート( int []arr){
        (arr == null && arr.length < 2) の場合 {
戻る;
        }
        ブール値 isSwap;
        // 外側のループは比較ラウンドの回数を制御します
( int i = 0; i < arr.length - 1; i++) {
            isSwap = false ;
            // 内側のループは隣接する要素を比較します
( int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) { // 前の数字が後ろの数字より大きい場合は、入れ替える
                    スワップ(arr, j, j + 1);
                    スワップ = true ;
                }
            } 
 
            スワップの場合
return ; // コードの最適化。ループ内で要素が入れ替わらない場合は、配列がすでに整列していることを意味します。
            }
        }
    } 
 
    /**
     * 3番目の数字を使わずに2つの数字を入れ替える
     *
     * @param arr
     * @パラメータ i
     * @param j
     */
公共 静的void swap( int [] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    } 
 
 //公共 静的void swap( int [] arr, int i, int j) {
 //整数  temp = arr[i];
 // arr[i] = arr[j];
 // arr[j] = temp ;
 // } 
 
 //公共 静的void swap( int [] arr, int a, int b) {
 // arr[a] = arr[a] + arr[b];
 // arr[b] = arr[a] - arr[b];
 // arr[a] = arr[a] - arr[b];
 // }
 }

2. 挿入ソート

挿入ソートの動作原理は、順序付けられたシーケンスを構築することです。ソートされていないデータの場合は、ソートされたシーケンスを後ろから前へスキャンし、対応する位置を見つけて挿入します。挿入ソートは通常、インプレースソート（つまり、O(1)の追加スペースのみを必要とするソート）によって実装されます。したがって、後ろから前へスキャンするプロセスでは、最新の要素を挿入するためのスペースを確保するために、ソートされた要素を繰り返し後方に移動する必要があります。

アイデア:

最初の要素から始めて、要素はソートされているとみなすことができます。
次の要素を取り出し、ソートされた要素の順序で後ろから前へスキャンします。
要素（すでにソートされている）が新しい要素より大きい場合は、要素を次の位置に移動します。
ソートされた要素が新しい要素以下になる位置が見つかるまで、手順 3 を繰り返します。
その位置に新しい要素を挿入した後;
手順2～5を繰り返します。

コード実装:

パッケージ com.nateshao.basic_01_ten_sort; 
 
 /**
 * @日付Shao Tongjieによって2021/10/29 21:56に作成
 * @WeChatパブリックアカウントプログラマーQianyu
 * 個人ウェブサイト www.nateshao.cn
 * @ブログ https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * 説明：
 */
パブリッククラス Code_02_InsertionSortTest {
公共 静的void main(String[] args) {
 int [] arr = {3、44、38、5、47、15、36、26、27、2、46、4、19、50、48};
        挿入ソート(arr);
 ( int i = 0; i < arr.length; i++) {
            システム.out.print (arr[i] + " " );
        }
    } 
 
公共 静的void挿入ソート( int []arr){
        (arr == null || arr.length < 2) の場合 {
戻る;
        }
 ( int i = 1; i < arr.length; i++) {
 ( int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j -- ) {  
                スワップ(arr, j, j + 1);
            }
        }
    } 
 
公共 静的void swap( int [] arr, int i, int j) {
整数  temp = arr[i];
        arr[i] = arr[j];
        arr[j] =一時;
    }
 }

3. シェルソート

シェルソートは挿入ソートの改良版です。

挿入ソートは、基本的にすでに順序付けられている配列をソートするのに効率的ですが、要素を移動する場合、交換できるのは隣接する 2 つの要素のみです。シェルソートは、交換される要素が隣接する要素に限定されないようにギャップを追加します。間隔は徐々に狭くなり、1 に減少すると、配列は基本的に順序付けられます。

大きな間隔の順序は間隔を縮小しても崩れない

コード実装:

パッケージ com.nateshao.basic_01_ten_sort; 
 
 java.util.Arrays をインポートします。 
 
 /**
 * @日付Shao Tongjieによって2021/10/30 10:44に作成
 * @WeChatパブリックアカウントプログラマーQianyu
 * 個人ウェブサイト www.nateshao.cn
 * @ブログ https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * 説明: シェルソート
 */
パブリッククラス Code_04_ShellSort {
公共 静的void main(String[] args) {
 int [] arr = {3、44、38、5、47、15、36、26、27、2、46、4、19、50、48};
        シェルソート(arr);
        System.out.println (Arrays.toString(arr)) ;
        シェルソート1(arr);
        System.out.println (Arrays.toString(arr)) ;
    } 
 
    /**
     * シェルソートは順序付けられたシーケンスに挿入するときに交換メソッドを使用します
     *
     * @param arr
     */
公共 静的voidシェルソート( int []arr){
        (arr == null && arr.length < 2) の場合 {
戻る;
        }
        //ギャップを増やし、徐々に増分を減らす
( intギャップ = arr.length / 2; ギャップ > 0; ギャップ /= 2) {
            //ギャップ要素から始めて、それが属するグループを1つずつ直接挿入して並べ替えます
( int i = ギャップ; i < arr.length; i++) {
整数j = i;
                (j - ギャップ >= 0 && arr[j] < arr[j - ギャップ]) {
                    // 挿入ソートは交換法を使用する
                    swap(arr, j, j - ギャップ);
                    j -= ギャップ;
                }
            }
        }
    } 
 
    /**
     * シェルソートでは、順序付けられたシーケンスに挿入するときに移動メソッドが使用されます。
     *
     * @param arr
     */
公共 静的void shellSort1( int [] arr) {
        (arr == null && arr.length < 2) の場合 {
戻る;
        }
        //ギャップを増やし、徐々に増分を減らす
( intギャップ = arr.length / 2; ギャップ > 0; ギャップ /= 2) {
            //ギャップ要素から始めて、それが属するグループを1つずつ直接挿入して並べ替えます
( int i = ギャップ; i < arr.length; i++) {
整数j = i;
整数  temp = arr[j];
                （arr[j] < arr[j - ギャップ]）の場合{
                    (j - ギャップ >= 0 && temp < arr[j - ギャップ]) {
                        //メソッドを移動
                        arr[j] = arr[j - ギャップ];
                        j -= ギャップ;
                    }
                    arr[j] =一時;
                }
            }
        }
    } 
 
公共 静的void swap( int [] arr, int a, int b) {
        arr[a] = arr[a] + arr[b];
        arr[b] = arr[a] - arr[b];
        arr[a] = arr[a] - arr[b]; 
 
    }
 }

4. 選択ソート

時間計算量、追加の空間計算量

まず、ソートされていないシーケンス内の最小 (最大) の要素を見つけて、ソートされたシーケンスの開始位置に格納します。次に、残りのソートされていない要素から最小 (最大) の要素を探し続け、ソートされたシーケンスの最後に配置します。すべての要素がソートされるまでこれを繰り返します。

アイデア:

配列内の最小（最大）の数値を見つける

現在走査中の配列の最初の要素と最小の数値を交換する

最初の2つの手順を繰り返して、トラバーサル配列の範囲を狭めます。

コード実装:

パッケージ com.nateshao.basic_01_ten_sort; 
 
 /**
 * @日付Shao Tongjieによって2021/10/29 22:51に作成
 * @WeChatパブリックアカウントプログラマーQianyu
 * 個人ウェブサイト www.nateshao.cn
 * @ブログ https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * 説明: 並べ替えを選択
 */
パブリッククラス Code_03_SelectionSortTest {
公共 静的void main(String[] args) {
 int [] arr = {3、44、38、5、47、15、36、26、27、2、46、4、19、50、48};
        選択ソート(arr);
 ( int i = 0; i < arr.length; i++) {
            システム.out.print (arr[i] + " " );
        }
    } 
 
公共 静的void選択ソート( int []arr){
整数 分;
 ( int i = 0; i < arr.length - 1; i++) {
 min = i; // デフォルトでは、現在ソートされている配列の最初の要素が最小値になります
( int j = i + 1; j < arr.length; j++) {
                if (arr[ min ] > arr[j]) { // より小さな最小インデックスを見つける
最小値= j;
                }
            } 
 
            もし (i != min ) {
                スワップ(arr, i, min );
            }
        }
    } 
 
公共 静的void swap( int [] arr, int i, int j) {
整数  temp = arr[i];
        arr[i] = arr[j];
        arr[j] =一時;
    }
 }

5. クイックソート

ソートパスにより、ソートするデータは 2 つの独立した部分に分割され、一方の部分のすべてのデータはもう一方の部分のすべてのデータよりも小さくなります。次に、この方法に従って、2 つの部分のデータが別々にすばやくソートされます。ソートプロセス全体を再帰的に実行して、データ全体を順序付けられたシーケンスに変換できます。

アイデア:

左の最初の数字を基本値として取る
右から左へトラバースして参照番号より小さい値を見つけ、それを左側の位置に割り当てます。
左から右へ移動して参照番号より小さい値を見つけ、それを右側の位置に割り当てます。
左と右の人差し指が合うまで2、3を繰り返します
会議が行われる座標に参照値を配置します。
ピボット値の左と右のサブ配列を再帰的に返します

パッケージ com.nateshao.basic_01_ten_sort; 
 
 java.util.Arrays をインポートします。 
 
 /**
 * @日付Shao Tongjieによって2021/10/30 12:09に作成
 * @WeChatパブリックアカウントプログラマーQianyu
 * 個人ウェブサイト www.nateshao.cn
 * @ブログ https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * 説明: クイックソート
 */
パブリッククラス Code_05_QuickSort {
公共 静的void main(String[] args) {
 int [] arr = {3、44、38、5、47、15、36、26、27、2、46、4、19、50、48};
        クイックソート(arr, 0, arr.length - 1);
        System.out.println (Arrays.toString(arr)) ;
    } 
 
    /**
     * @param arr ソートする列
     * @param leftIndex ソートする列の開始位置
     * @param rightIndex ソートする列の終了位置
     */
    プライベート静的voidクイックソート( int [] arr、 int左インデックス、 int右インデックス) {
        /**
         * 左辺が右辺より大きい場合は、直接戻ります
         */
        左インデックス >= 右インデックスの場合 {
戻る;
        } 
 
整数 左= 左インデックス;
整数 右= 右インデックス;
        //ソートされる最初の要素が参照値として使用されます
整数 キー= arr[左]; 
 
        // left = rightになるまで、左側と右側を交互にスキャンします 
        （左<右）{
            while (右>左&& arr[右] >=キー) {
                //右から左にスキャンして、参照値より小さい最初の要素を見つけます
右- ;  
            } 
 
            // この要素を見つけて、arr[ right ] を arr[ left ]に格納します。
            arr[左] = arr[右]; 
 
            while (左<右&& arr[左] <=キー) {
                //左から右にスキャンして、参照値より大きい最初の要素を見つけます
左++;
            } 
 
            // この要素を見つけて、arr[ left ] を arr[ right ]に格納します。
            arr[右] = arr[左];
        }
        //参照値を返す
        arr[左] =キー;
        //参照値の左側の要素を再帰的にソートする
        クイックソート(arr, 左インデックス,左- 1);
        // 基本値の右側の要素を再帰的にソートします。
        クイックソート(arr,右+ 1, 右インデックス);
    }
 }

6. マージソート

時間計算量、追加の空間計算量

マージソートは、マージ操作に基づいた効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法の非常に典型的な応用です。順序付けられたサブシーケンスをマージして、完全に順序付けられたシーケンスを取得します。つまり、最初に各サブシーケンスを順序付けし、次にサブシーケンスのセグメントを順序付けます。 2 つの順序付きリストが 1 つの順序付きリストに結合される場合は、双方向結合と呼ばれます。マージソートは安定したソート方法です。

アイデア:

2 つのソートされたシーケンスの合計サイズを持つスペースを申請します。このスペースは、結合されたシーケンスを格納するために使用されます。

2 つのポインタを設定します。その初期位置は、2 つのソートされたシーケンスの開始位置になります。

2つのポインタが指す要素を比較し、比較的小さい要素を選択してマージスペースに配置し、ポインタを次の位置に移動します。

ポインタがシーケンスの最後に到達するまでステップ3を繰り返します。

他のシーケンスの残りの要素をすべて、結合されたシーケンスの末尾に直接コピーします。

例えば：

例: 配列A: [4,6,9] 配列B: [3, 2, 1]

まず配列 A と B をソートします。配列 A と B。新しい配列 C を定義します。配列 A を比較し、小さい方を前に置きます。配列Aをソートした後、配列Bを配列Cにコピーします。

C配列: [1,2,3,4,6,9]

コード実装:

パッケージ com.nateshao.basic_01_ten_sort; 
 
 java.util.Arrays をインポートします。 
 
 /**
 * @日付Shao Tongjieによって2021/10/30 12:15に作成
 * @WeChatパブリックアカウントプログラマーQianyu
 * 個人ウェブサイト www.nateshao.cn
 * @ブログ https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * 説明：
 */
パブリッククラス Code_06_MergeSort {
公共 静的void main(String[] args) {
整数テスト時間 = 500000;
最大サイズ = 20;
整数最大値 = 100;
        ブール値 成功 = true ;
 ( int i = 0; i < testTime; i++)の場合{
 int [] arr1 = ランダム配列を生成します(maxSize、maxValue);
 int [] arr2 = copyArray(arr1);
            マージソート(arr1);
            コンパレータ(arr2);
            （！isEqual（arr1、arr2））の場合{
                成功 = false ;
                printArray(arr1);
                printArray(arr2);
                壊す;
            }
        }
        System.out.println (succeed? 「いいね！」 : 「最悪！」 ); 
 
 int [] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        マージソート(arr);
        printArray(arr); 
 
    }
    /**
     * 配列の長さが空の場合、または配列の長さが 1 の場合。比較せずに直接返す
     * @param arr
     */
公共 静的voidマージソート( int []arr){
        (arr == null || arr.length < 2) の場合 {
戻る;
        }
        マージソート(arr, 0, arr.length - 1);
    } 
 
    /**
     * この範囲には数字が1つしかないので、それを直接返します
     * @param arr
     * @param l
     * @param r
     */
公共 静的void mergeSort( int [] arr, int l, int r) {
        もし（l == r）{
戻る;
        }
 int mid = l + ((r - l) >> 1); // LとRの中点 (L + R) / 2
        mergeSort(arr, l, mid); // 左部分をソートする T(n/2)
        mergeSort(arr, mid + 1, r); // 右側の部分をソートする T(n/2)
        merge(arr, l, mid, r); // 左部分と右部分をマージする O(n)
        // 合計時間計算量: T(N) = 2T(n/2) + O(N)
    } 
 
公共 静的voidマージ( int [] arr, int l, int m, int r) {
 int [] help = 新しいint [r - l + 1];
整数i = 0;
 int p1 = l; // 配列 l、左側の最初の配列の最小値。
 int p2 = m + 1; // 右側の最初のものの最小値。
        while (p1 <= m && p2 <= r) { // p1とp2のどちらか小さい方を新しい配列に入れて、配列を再ソートします
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        /**
         * p1、p2、2つの数値のうち1つは範囲外である必要があります
         */
        (p1 <= m) の間 {
            help[i++] = arr[p1++];
        }
        (p2 <= r) の間
            help[i++] = arr[p2++];
        }
 (i = 0; i < help.length; i++)の場合{
            arr[l + i] = help[i]; // 最後に配列をarr[i]にコピーします
        }
    } 
 
    /**
     * コンパレータ
     * @param arr
     */
公共 静的voidコンパレータ( int []arr){
        配列.sort(arr);
    } 
 
    /**
     * 任意の配列を生成する
     * @param 最大サイズ
     * @param 最大値
     * @戻る 
     */
公共 静的  int [] ランダム配列を生成する( int最大サイズ、 int最大値) {
 int [] arr = 新しいint [( int ) ((maxSize + 1) * Math.random())];
 ( int i = 0; i < arr.length; i++) {
            arr[i] = ( int ) ((maxValue + 1) * Math.random()) - ( int ) (maxValue * Math.random());
        }
 arrを返します。
    } 
 
    /**
     * 配列をコピー
     * @param arr
     * @戻る 
     */
公共 静的  int [] コピー配列( int [] arr) {
        もしarr == nullの場合{
戻る ヌル;
        }
 int [] res = 新しいint [arr.length];
 ( int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
 resを返します。
    } 
 
    /**
     * 2 つの配列は等しいですか?
     * @パラメータ arr1
     * @param arr2
     * @戻る 
     */
公共 静的ブール値isEqual( int [] arr1, int [] arr2) {
        ((arr1 == null && arr2 != null ) || (arr1 != null && arr2 == null )) {
戻る 間違い;
        }
        (arr1 == null && arr2 == null )の場合{
戻る 真実;
        }
        (arr1の長さ!= arr2の長さ)の場合{
戻る 間違い;
        }
 ( int i = 0; i < arr1.length; i++) {
            (arr1[i] != arr2[i]) の場合 {
戻る 間違い;
            }
        }
戻る 真実;
    } 
 
    /**
     * 配列を印刷する
     * @param arr
     */
公共 静的void printArray( int []arr){
        もしarr == nullの場合{
戻る;
        }
 ( int i = 0; i < arr.length; i++) {
            システム.out.print (arr[i] + " " );
        }
        System.out.println( ) ;
    }
 }

7. カウントソート

カウンティングソートはバケットソートの一種です。これは非比較ベースのソートアルゴリズムです。

その利点は、特定の範囲内で整数をソートする場合、その複雑さは (k は整数の範囲) であり、どの比較ソートアルゴリズムよりも高速であることです。もちろん、これは時間と引き換えにスペースを犠牲にする手法であり、その時点では比較ベースのソートほど効率は良くありません。

アイデア:

配列内の最大値と最小値を見つける
対応する長さ（最大 - 最小 + 1）の配列を作成します。
各数字の出現回数を数える array[val - min]++
ターゲット配列を埋める

コード実装:

パッケージ com.nateshao.basic_01_ten_sort; 
 
 java.util.Arrays をインポートします。 
 
 /**
 * @日付Shao Tongjieによって2021/10/30 14:38に作成
 * @WeChatパブリックアカウントプログラマーQianyu
 * 個人ウェブサイト www.nateshao.cn
 * @ブログ https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * 説明: カウントソート
 * オリジナルリンク: https://baijiahao.baidu.com/s?id=1613842852280800384&wfr=spider& for =pc
 */
パブリッククラス Code_07_CountSort { 
 
公共 静的void main(String[] args) {
 int [] 配列 = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
 int [] sortedArray = countSort(配列);
        システム.out.println (Arrays.toString(sortedArray));
    } 
 
公共 静的  int [] countSort( int [] 配列) {
        //1. 系列の最大値と最小値を取得し、その差を計算する
整数 最大値= 配列[0];
整数 最小値= 配列[0];
 ( int i = 1; i < 配列の長さ; i++) {
            配列[i] >最大値の場合
最大値= 配列[i];
            }
            配列[i] < minの場合
min = 配列[i];
            }
        }
 int d =最大値-最小値;
        //2. 統計配列を作成し、対応する要素の数を数える
int [] countArray = 新しいint [d + 1];
 ( int i = 0; i < 配列の長さ; i++) {
            countArray[配列[i] - min ]++;
        }
        //3. 統計配列を変換します。次の要素は前の要素の合計に等しくなります。
整数 合計= 0;
 ( int i = 0; i < countArray.length; i++) {
合計+= countArray[i];
            countArray[i] =合計;
        }
        //4. 元のシーケンスを逆順に走査し、統計配列から正しい位置を見つけて、結果配列に出力します。
 int [] sortedArray = 新しいint [array.length];
 ( int i = array.length - 1; i >= 0; i --) {  
            sortedArray[countArray[配列[i] - min ] - 1] = 配列[i];
            countArray[配列[i] - min ] --;  
        }
ソートされた配列を返します。
    }
 }

カウントソートの制限:

1. シーケンスの最大値と最小値の差が大きすぎる場合、カウントソートは適用できません。

たとえば、0 から 1 億までの範囲の 20 個のランダムな整数が与えられた場合、カウントソートを使用すると、長さ 1 億の配列を作成する必要があります。スペースが大幅に無駄になるだけでなく、時間の複雑さも増大します。

2. シーケンスの要素が整数でない場合は、カウントソートは適用できません。

シーケンス内のすべての要素が 25.213 や 0.00000001 などの小数の場合、対応する統計配列を作成できません。これは明らかにカウントソートには使用できません。

8. 基数ソート

基数ソートはバケットソートの一種です。原理としては、整数を桁数に応じて異なる数値に分割し、各桁を個別に比較します。各ビットの比較が完了すると、配列は並べ替えられます。最上位ビットを比較すると、配列は順序付けられたシーケンスになります。

コード実装:

パッケージ com.nateshao.basic_01_ten_sort; 
 
 java.util.Arrays をインポートします。 
 
 /**
 * @日付Shao Tongjieによって2021/10/30 15:15に作成
 * @WeChatパブリックアカウントプログラマーQianyu
 * 個人ウェブサイト www.nateshao.cn
 * @ブログ https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * 説明: 基数ソート
 * オリジナルリンク: https://blog.csdn.net/weixin_44537194/article/details/87302788
 */
パブリッククラス Code_08_RadixSort {
公共 静的void main(String[] args) {
 int [] 配列 = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        radixSort(配列);
        システム.out.println (Arrays.toString(array));
    } 
 
公共 静的void radixSort( int [] arr) {
        // ループ回数を知るために、配列に最大の数値を保存します
整数  max = Integer .MIN_VALUE; // (最小の整数)
        // 配列を走査して最大値を見つける
( int i = 0; i < arr.length; i++) {
            （最大値<arr[i]）の場合{
最大値= arr[i];
            }
        } 
 
        // 最大桁数を計算する。この方法は非常に賢い
int最大長さ = (最大+ "" ).length();
        // データを一時的に保存するための配列
int [][] temp = 新しいint [10][arr.length];
        // バケット内の要素の位置を格納するために使用します
int [] counts = new int [arr.length]; 
 
        // 最初の 1 桁の数字は余りを得るのが簡単です。2 番目のラウンドは 10 で割って余りを出し、その後 100 の位の数字を 100 で割ります。
        // ご覧のとおり、ループ回数に応じて変化する別の変数があります。 
 
        //ループ回数
( int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            // 各ラウンドの残りを取る
( int j = 0; j < arr.length; j++)の場合{
                // 余りを計算する
int ys = (arr[j] / n) % 10;
                // コンビニエンスストアのデータを指定された配列に格納します。格納するバケットと格納する順序の 2 つの情報があります。
 temp [ys][counts[ys]] = arr[j];
                //レコード数
                counts[ys]++;
            } 
 
            //記録する数字は、次の位置に配置する必要があります
整数 インデックス= 0;
            // 各ループの後に数字を取り出す
( int k = 0; k < counts.length; k++) {
                // レコード数の配列内の現在の残余レコードはゼロではありません
                カウント[k]が0の場合
( int l = 0; l < counts[k]; l++) {
                        // 要素を取得する
                        arr[インデックス] = temp [k][l];
インデックス++;
                    }
                    // 取り出した後に数量をゼロにする
                    カウント[k] = 0;
                }
            }
        }
    }
 }

9. バケットソート

バケットソート、またはビンソートは、配列を有限数のバケットに分割することによって機能するソートアルゴリズムです。各バケットは個別にソートされます。

アイデア:

空のバケットとして使用する配列の固定数を設定します。
シーケンスを検索し、アイテムを 1 つずつ対応するバケットに入れます。
空ではない各バケットをソートします。
空ではないバケットからアイテムを元の順序に戻します。

コード実装:

パッケージ com.nateshao.basic_01_ten_sort; 
 
 java.util.ArrayList をインポートします。
 java.util.Arrays をインポートします。
 java.util.List をインポートします。
 java.util.Random をインポートします。 
 
 /**
 * @日付Shao Tongjieによって2021/10/30 15:56に作成
 * @WeChatパブリックアカウントプログラマーQianyu
 * 個人ウェブサイト www.nateshao.cn
 * @ブログ https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * 説明: バケットソート
 */
パブリッククラス Code_09_BucketSort { 
 
公共 静的void main(String[] args) {
 int [] arr = {3、44、38、5、47、15、36、26、27、2、46、4、19、50、48};
        バケットソート(arr);
        System.out.println (Arrays.toString(arr)) ;
    } 
 
公共 静的voidバケットソート( int []arr){
整数 最大値= arr[0];
整数 最小値= arr[0];
 ( int i = 1; i < arr.length; i++) {
            （最大値<arr[i]）の場合{
最大値= arr[i];
            }
            もし（最小値＞arr[i]）{
最小値= arr[i];
            }
        }
 int bucketNum = ( max - min ) / 10 + 1; // バケットの数
        List[] バケット = 新しいArrayList[bucketNum];
 ( int i = 0; i < バケットの長さ; i++) {
            バケット[i] = 新しいArrayList <Integer> ();
        } 
 
        // 要素をバケットに入れる
( int i = 0; i < arr.length; i++) {
 int a = (arr[i] - min ) / 10;
            バケット[a] .add (arr[i]);
        } 
 
整数 インデックス= 0;
 for (List< Integer > b : バケット) {
            insertionSort(b); // バケット内の要素をソートする
for (整数num : b) {
                arr[ index ++] = num; // ソートされた要素を取り出す
            }
        }
    } 
 
    // 挿入ソート
公共 静的void挿入ソート(リスト<整数> arr) {
 ( int i = 1; i < arr.size ( ) ); i++) {
            // 2番目から始めて、前のものより小さいかどうかを確認します
            （arr.get(i) < arr.get(i - 1)）の場合{
                // 1つずつ前方に検索します。この数より大きい場合は、1つ前に戻ります
整数  temp = arr.get(i);
整数j = i - 1;
                j >= 0 && temp < arr.get(j) の場合{
                    arr.set (j + 1, arr.get(j));
                    j --;  
                }
                // それより小さい数値を探し、それをこの数値の後の要素に代入します 
                arr.set (j+1, temp );
            }
        }
    }
 }

10. ヒープソート

ヒープソートとは、ヒープデータ構造を使用して設計されたソートアルゴリズムを指します。ヒープは、完全なバイナリツリーを近似し、ヒープの特性を満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードよりも小さい (または大きい) です。ヒープは完全な二分木です。完全な二分木とは、上から下、左から右に欠けているノードがない木です。簡単に言えば、ノードに右サブツリーがある場合、左サブツリーも存在する必要があります。

ヒープソートの説明:

上の図では、ノード 3 には右サブツリーがありますが、左サブツリーがないため、これは完全なバイナリツリーではありません。

ヒープは、大きなトップヒープと小さなトップヒープに分割されます。

最大ヒープの親ノードの値は子ノードの値以上である
小さなトップヒープの親ノードの値は子ノードの値以下です

配列内のすべての要素をヒープにマップすると、そのインデックスは次の関係にあることがわかります。左ノードのインデックス = 親ノード * 2 + 1 右ノードのインデックス = 親ノード * 2 + 2

最大ヒープの場合、ルートノードがその最大値になります。ランダム配列をヒープに変換するには、上記の関係に従って親ノードと子ノードの要素を交換するだけです。次に、ルートノードと最後のノードを交換します。次に、配列の長さを短くします。配列をヒープに変換するときに、配列内の最大の数値を取得して、それを配列の末尾に移動することもできます。ヒープを変換しています...

アイデア:

配列全体をヒープに構築する

ルートノードと最後のノードを入れ替える

ルートノードからheapifyを開始する

すべての要素が走査されるまで 2 と 3 を繰り返します。

コード実装:

パッケージ com.nateshao.basic_class_01; 
 
 java.util.Arrays をインポートします。 
 
パブリッククラス Code_03_HeapSort { 
 
公共 静的void main(String[] args) {
整数テスト時間 = 500000;
最大サイズ = 20;
整数最大値 = 100;
        ブール値 成功 = true ;
 ( int i = 0; i < testTime; i++)の場合{
 int [] arr1 = ランダム配列を生成します(maxSize、maxValue);
 int [] arr2 = copyArray(arr1);
            ヒープソート(arr1);
            コンパレータ(arr2);
            （！isEqual（arr1、arr2））の場合{
                成功 = false ;
                壊す;
            }
        }
        System.out.println (succeed? 「素晴らしい！」 : 「最悪だ！」 ); 
 
 int [] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        ヒープソート(arr);
        printArray(arr);
    } 
 
    /**
     * ヒープソート
     * @param arr
     */
公共 静的voidヒープソート( int []arr){
        (arr == null || arr.length < 2) の場合 {
戻る;
        }
        // 大きなルートヒープを作成する
( int i = 0; i < arr.length; i++) {
            ヒープ挿入(arr, i);
        }
整数 サイズ= arr.length;
        swap(arr, 0, --size); // 最後の桁が最初の桁と入れ替わります。 ヒープサイズマイナス1  
        (サイズ> 0)の場合
            heapify(arr, 0, size ); // 大きなルートヒープの調整を続ける
            swap(arr, 0, --size); // 続行します。最後の桁が最初の桁と入れ替わります。 ヒープサイズマイナス1  
        }
    } 
 
    /**
     * 大きな根の山を作る
     *
     * @param arr
     * @paramインデックス 
     */
公共 静的voidヒープ挿入( int []arr, int  索引） {
        (arr[インデックス] > arr[(インデックス- 1) / 2]) {
            swap(arr,インデックス, (インデックス- 1) / 2);
インデックス= (インデックス- 1) / 2;
        }
    } 
 
公共 静的voidヒープ化( int []arr, int  インデックス、 int  サイズ） {
整数  left = index * 2 + 1; // 左の子。 i*2+1 右の子:左+ 1
        while ( left < size ) { // ヒープサイズ
            //左の子と子を比較し、値の大きい方を取得します
int largest = left + 1 < size && arr[ left + 1] > arr[ left ] ? left + 1 : left ;
            // ノードをその左と右の子と比較し、大きい方のインデックスを取得します
            最大 = arr[最大] > arr[インデックス] ? 最大:インデックス;
            // 私なら続ける必要はありません
            if (最大 ==インデックス) {
                壊す;
            }
            swap(arr, largest, index ); // largest != index  
インデックス= 最大;
左=インデックス* 2 + 1;
        }
    } 
 
公共 静的void swap( int [] arr, int i, int j) {
 tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    } 
 
公共 静的voidコンパレータ( int []arr){
        配列.sort(arr);
    } 
 
公共 静的  int [] ランダム配列を生成する( int最大サイズ、 int最大値) {
 int [] arr = 新しいint [( int ) ((maxSize + 1) * Math.random())];
 ( int i = 0; i < arr.length; i++) {
            arr[i] = ( int ) ((maxValue + 1) * Math.random()) - ( int ) (maxValue * Math.random());
        }
 arrを返します。
    } 
 
公共 静的  int [] コピー配列( int [] arr) {
        もしarr == nullの場合{
戻る ヌル;
        }
 int [] res = 新しいint [arr.length];
 ( int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
 resを返します。
    } 
 
公共 静的ブール値isEqual( int [] arr1, int [] arr2) {
        ((arr1 == null && arr2 != null ) || (arr1 != null && arr2 == null )) {
戻る 間違い;
        }
        (arr1 == null && arr2 == null )の場合{
戻る 真実;
        }
        (arr1の長さ!= arr2の長さ)の場合{
戻る 間違い;
        }
 ( int i = 0; i < arr1.length; i++) {
            (arr1[i] != arr2[i]) の場合 {
戻る 間違い;
            }
        }
戻る 真実;
    } 
 
公共 静的void printArray( int []arr){
        もしarr == nullの場合{
戻る;
        }
 ( int i = 0; i < arr.length; i++) {
            システム.out.print (arr[i] + " " );
        }
        System.out.println( ) ;
    }
 }