6つの主要なソートアルゴリズム

6 つの一般的なソートアルゴリズムの GIF アニメーションがあり、ソートの考え方をより簡単に理解するのに役立ちます。

6つの分類は以下の通りです👇

バブルソート、カウンティングソート、クイックソート、マージソート、挿入ソート、選択ソート、時間計算量は次のとおりです👇

ソートアルゴリズムの複雑さの分析
バブルソート
以下のGIFはZhihu Handsomeからのものです

バブルソート
名前の由来は、泡のように浮かんでいることからきています。よく考えてみると、隣接する 2 つの要素の大きさをその都度比較し、ゆっくりと「浮かび上がって」いくことを意味します。その考え方を見てみましょう。

「時間計算量 O(n*n)」

アイデア
1 隣接する要素を比較します。前者が後者よりも大きい場合は、それらの位置を交換します。
2 最初のペアから最後のペアまで、隣接する要素の各ペアに対して同じ操作を実行し、最後の要素が最大要素になるようにします。
3 各ループの最後の要素を除いて、n 個の要素に対して上記の手順を繰り返します。
4 並べ替えが完了するまで手順 1 ～ 3 を繰り返します。

コードの実装

// 最も外側のループ制御の内容はループの数です
// 各比較は、隣接する2つの間のサイズ関係です
BubbleSort =関数(arr, flag = 0) とします。
    len = arr.lengthとします
 
 (i = 0; i < len - 1; i++)の場合{
 (j = 0; j < len - 1 - i; j++)の場合{
            もし(arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
戻りフラグ? arr.reverse(): arr
 } 
 
 arr = [2, 9, 6, 7, 4, 3, 1, 7]とします。
 console.log(バブルソート(arr, 1))

カウントソート
名前が示すように、その考え方は、配列要素を配列の添え字として使用し、一時配列を使用して要素の出現回数をカウントすることです。

配列内のデータは整数である必要があり、最大値と最小値の差は大きすぎてはいけません。データが負の場合、私が実装したソリューションにはこれに対する最適化があります。

「時間計算量: O(n+k)」

アイデア
1.差dを計算し、最小値が0未満の場合、それ自身を加算する

2. 統計配列を作成し、対応する要素の数を数える

3. 統計配列を、次の要素が前の要素の合計と等しくなるように変換します。つまり、ランキング配列です。

4. 元の配列を走査し、統計配列から正しい位置を見つけ、結果配列に出力します。

アニメーション

カウントソート
コードの実装

// カウントソート
countingSort =関数(arr, flag = 0) とします。
    min = arr[0]とします。
最大値= arr[0],
        len = 配列の長さ;
    // 最大値と最小値を見つける
(i = 0; i < len; i++)の場合{
 max = Math.max (arr[i], max )です。
 min = Math. min (arr[i], min )
    }
    // 1. 差dを計算し、最小値が0未満の場合、それ自身を加算する  
 
    d = max - minとすると、
追加= min < 0 ? - min : 0;
    //2. 統計配列を作成し、対応する要素の数を数える
    countArray = new Array(d+1+ add ).fill(0)とします。
 (i = 0; i < len; i++)の場合{
        demp = arr[i]- min + addとする 
        countArray[ demp ] += 1
    } 
     
    //3. 統計配列を変換します。次の要素は前の要素の合計に等しくなります。つまり、ランキング配列です。
    合計を0 とします。 
 
    // ここで走査する必要があるのは countArray 配列の長さです
(i = 0 とすると、i < d+1+ が追加され、i++ となる){
合計+= countArray[i]
        countArray[i] =合計;
    }
    res = new Array(len) とします。
    //4. 元の配列を走査し、統計配列から正しい位置を見つけ、結果配列に出力します。
 (i = 0; i < len; i++)の場合{
        demp = arr[i] - min + addとする 
        res[ countArray[demp] -1 ] = arr[i]
        countArray[demp] --;  
    }
戻りフラグ? res.reverse(): res
 } 
 
 arr = [2, 9, 6, 7, 4, 3, 1, 7,0,-1,-2]とします。
 console.log(countingSort(arr))

クイックソート
基本的な考え方: ソートパスによって、ソートするレコードは 2 つの独立した部分に分割されます。レコードの一方の部分のキーワードがもう一方の部分のキーワードよりも小さい場合、レコードの 2 つの部分を個別にソートして、シーケンス全体の順序を実現できます。

「時間計算量: O(nlogn)」

アイデア<br /> 配列の中央の数字をカーディナリティとして選択し、このカーディナリティを配列から取り出して 2 つの配列コンテナーを準備し、配列をトラバースして、それらを 1 つずつカーディナリティと比較し、小さい方を左のコンテナーに、大きい方を右のコンテナーに配置します。
2 つのコンテナの要素を再帰的に処理し、処理されたデータとベースをサイズ別に配列にマージして返します。
アニメーション

クイックソート

クイックソート =関数(arr) {
    // 再帰終了は配列の長さ1です
    (arr.length <= 1)の場合、 arrを返す
    // 中央の値のインデックスを取得し、Math.floor を使用して切り捨てます。
    インデックス= Math.floor(arr.length / 2)とします。
    // splice を使用して中間の値をインターセプトします。最初のパラメーターはインターセプト インデックスで、2 番目のパラメーターはインターセプトの長さです。
    // ここで pivot=arr[ index ] を使用すると、無限再帰エラーが発生します。
    // スプライスは元の配列に影響します
    ピボット = arr.splice(インデックス, 1)[0] とします。
左= [],
右= [];
    コンソール.log(ピボット)
    コンソールログ(arr)
 ( i = 0 とします; i < arr.length; i++) {
        ピボット > arr[i] の場合 {
左.push(arr[i])
        }それ以外{
右.push(arr[i])
        }
    }
 quickSort( left ).concat([pivot], quickSort( right ));を返します。
 } 
 
 //arr = [2, 9, 6, 7, 4, 3, 1, 7]とします
// console.log(クイックソート(arr))

マージソート

2つの順序付けられたシーケンスを1つの順序付けられたシーケンスに結合することを「マージ」と呼びます。

基本的な考え方とプロセス: 最初にシーケンスを再帰的に分解し、次にシーケンスをマージします (分割統治思考の典型的な応用)

「時間計算量: O(nlog(n))」

アイデア<br /> 配列を A と B の 2 つのグループに分割し、各グループに要素が 1 つだけになるまで 2 つのグループの分割を続けます。
グループは分割プロセスに従って徐々に結合されます。各グループには最初は要素が 1 つしかないため、グループは順序付けられていると見なすことができます。グループの結合は、順序付けられた 2 つの配列を結合するプロセスと見なすことができます。
各間隔に数字が 1 つだけになるまで、左側と右側の 2 つの小数点シリーズに対して 2 番目の手順を繰り返します。
アニメーション

マージソート
コードの実装

const merge = ( left , right ) => { // 配列をマージする
 
    結果 = []
    // 遅延するにはshift()メソッドを使用し、最初の要素を削除して値を返します
    while (左.長さ &&右.長さ) {
        （左[0] <=右[0]）の場合{
            結果.push(左.shift())
        }それ以外{
            結果.push(右.shift())
        }
    }
    while (左.長さ) {
        結果.push(左.shift())
    } 
 
    while (右.長さ) {
        結果.push(右.shift())
    }
結果を返す
} 
 
 mergeSort =関数(arr) {
    （arr.length <= 1）の場合
リターン
    mid = Math.floor(arr.length / 2) とします。
    // 配列を分割する
    左= arr.slice(0, mid) とします。
右= arr.slice(mid);
    mergeLeftArray = mergeSort(左) とします。
        mergeRightArray = mergeSort(右)
 merge(mergeLeftArray, mergeRightArray)を返します
} 
 
 arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]とします。
 console.log(マージソート(arr))

挿入ソート
名前が示すように、順序付けられたシーケンスを構築することで、ソートされていないデータの場合は、ソートされたシーケンス内で後ろから前へスキャンし、対応する位置を見つけて挿入します。

「時間計算量: O(n*n)」

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

コードの実装

挿入ソートを関数(arr)に代入する
    len = arr.lengthとします
 
 (i = 0; i < len; i++)の場合{
        preIndex = i - 1 とします。
            cur = arr[i];
        (preIndex >= 0 && arr[preIndex] > cur) の場合 {
            arr[プレインデックス + 1] = arr[プレインデックス]
            プレインデックス--;  
        }
        arr[preIndex + 1] = cur
    }
リターン
} 
 
 
 arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]とします。
 console.log(挿入ソート(arr))

選択ソート
アイデア: ソートが完了するまで、ソートする配列要素から最大 (最小) の要素を毎回最初の要素として選択します。

「時間計算量 O(n*n)」

アイデア
1. n個の数字があり、それをn-1回ソートする必要がある
2. 最初に最小値を選択し、それを最初に置く
3. 2回目の最小値を選択し、2番目の場所に置く
4. このプロセスを繰り返す
5. n-1回目の最小値を選択し、n-1番目の位置に配置する
コードの実装

selectSort = function (arr, flag = 0) とします。
    len = arr.lengthとします。
温度= 0; 
 
    // 合計len-1回のソート回数が必要です
(i = 0; i < len - 1; i++)の場合{
温度= i;
 (j = i + 1; j < len; j++)の場合{
            もし (arr[j] < arr[ temp ])
温度= j;
        }
        // 各トリップはi番目の桁が最小値であることを確認します
        if ( temp !== i) {
            [arr[i], arr[ temp ]] = [arr[ temp ], arr[i]]
        }
    } 
 
戻りフラグ? arr.reverse(): arr
 } 
 
 
 
 arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]とします。
コンソールログ(selectSort(arr, 1))