JavaScriptアルゴリズム マージソートアルゴリズム（詳細説明）

この記事では、マージ ソートの背後にあるロジックを学び、それを JavaScript で実装します。最後に、マージ ソートを空間と時間の複雑さの観点から他のアルゴリズムと比較します。

マージ ソートの背後にあるロジック

マージ ソートは、分割統治の概念を使用して、指定された要素のリストを並べ替えます。直接解決できるほど単純になるまで、問題を小さなサブ問題に分割します。

マージ ソートの手順は次のとおりです:

1. 指定されたリストを 2 つに分割します (リスト内の要素の数が奇数の場合は、それらをほぼ等しくします)。

2. 要素配列が 1 つだけ残るまで、同じ方法で部分配列の分割を続けます。

3. 単一要素配列から始めて、マージ サブ配列をマージして、マージされた各サブ配列をソートします。

4. 最終的に並べ替えられた配列が得られるまで、手順 3 を繰り返します。

配列 [4, 8, 7, 2, 11, 1, 3] を例として、マージ ソートがどのように機能するかを見てみましょう。

JavaScript を使用してマージ ソートを実装する

まず、2 つのソートされた部分配列を 1 つのソートされた配列にマージする関数を実装します。merge()。 2 つの部分配列はすでにソートされており、merge() 関数はそれらをマージするためにのみ使用されることに注意することが非常に重要です。 [推奨チュートリアル: "JavaScript ビデオ チュートリアル "]

は、次の 2 つのサブ配列を走査することで実現できます。

function merge(left, right) {
    let arr = []
    // 如果任何一个数组为空，就退出循环
    while (left.length && right.length) {
        // 从左右子数组的最小元素中选择较小的元素
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }
    
    // 连接剩余的元素，防止没有把两个数组遍历完整
    return [ ...arr, ...left, ...right ]
}

この関数では、2 つのサブ配列を配置することで、順序付きサブ配列 (left、right) を使用して、ソートされた大きな配列を取得します。まず、空の配列を作成します。次に、2 つのサブ配列 left と right の最小要素のうち小さい方を取得し、それを空の配列に追加します。 left および right サブ配列はソートされているため、それらの最初の要素をチェックするだけで済みます。

このプロセスでは、選択した要素がサブ配列から削除されます (shift() 関数によって実装されます)。サブ配列の 1 つが空になるまで、このプロセスを続けます。最後に、空ではない部分配列の残りの要素 (ソートされているため) をメイン配列の最後に挿入します。

これで、2 つのソートされた配列をマージするコードが完成しました。次に、マージ ソート アルゴリズムを実装する最終コードを示します。これは、要素が 1 つだけ含まれる配列になるまで配列の分割を続けることを意味します。

function mergeSort(array) {
  const half = array.length / 2
  
  if(array.length < 2){
    return array 
  }
  
  const left = array.splice(0, half)
  return merge(mergeSort(left),mergeSort(array))
}

コードでは、まず中点を決定し、splice() 関数を使用して配列を分割します。 2 つのサブ配列に分割します。要素数が奇数の場合は、左側の要素数が 1 つ減ります。単一要素の配列が残るまで配列を分割し続けます (array.length )。次に、前に実装した <code>merge() 関数を使用して部分配列をマージします。

コードを実装した後、前のユースケースでテストします:

array = [4, 8, 7, 2, 11, 1, 3];
console.log(mergeSort(array));

出力は期待どおりです:

1,2,3,4,7,8,11

マージソートの効率

マージ ソートの最悪の時間 計算量は $O(n\\log n)$ で、これはクイック ソートの最適な時間計算量と同じです。マージ ソートは、現在利用可能な最も高速なソート アルゴリズムの 1 つです。

クイック ソートとは異なり、マージ ソートは インプレース ソート アルゴリズムではないため、入力配列に加えて余分なスペースが必要になります。これは、サブ配列を格納するために補助配列を使用するためです。マージ ソートの空間計算量は $O(n)$ です。

マージ ソートのもう 1 つの利点は、分割された各半分を独立してソートできるため、マルチスレッドに非常に適していることです。マージ ソートの実行時間を短縮するもう 1 つの一般的な方法は、比較的小さなサブ配列 (約 7 要素) に達したときに挿入ソートを使用することです。これは、挿入ソートが小さい配列またはソートに近い配列に対して非常にうまく機能するためです。

概要

この記事では、マージ ソート アルゴリズムの背後にあるロジックについて学び、それを JavaScript で実装しました。これは基本的な並べ替えアルゴリズムの 1 つであり、分割統治戦略をより深く理解するのに役立ちます。

プログラミング関連の知識について詳しくは、プログラミング ビデオ コースをご覧ください。 ！

以上がJavaScriptアルゴリズム マージソートアルゴリズム（詳細説明）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。