JavaScriptアルゴリズムマージソートアルゴリズム（詳細説明）-jsチュートリアル-php.cn

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

青灯夜游

リリース： 2020-11-09 17:52:57

転載

4184 人が閲覧しました

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

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

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

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

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

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

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

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

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

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

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

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 < 2)。次に、前に実装した 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 要素) に達したときに挿入ソートを使用することです。これは、挿入ソートが小さい配列またはソートに近い配列に対して非常にうまく機能するためです。