JavaScript でのマージソートの概要 (コード例)

この記事では、JavaScript でのマージ並べ替えの概要 (コード例) を紹介します。必要な方は参考にしていただければ幸いです。

マージ ソート (MERGE-SORT) は、分割統治法 (pide) を使用するマージ操作に基づく効果的な並べ替えアルゴリズムです。 andConquer) は非常に典型的なアプリケーションです。すでに順序付けされているサブシーケンスをマージして、完全に順序付けされたシーケンスを取得します。つまり、まず各サブシーケンスを順序どおりにしてから、サブシーケンス セグメントを順序どおりにします。 2 つの順序付きリストが 1 つの順序付きリストにマージされる場合、それは双方向マージと呼ばれます。

マージ ソート

マージ ソートは、平均、最良、最悪にかかわらず、時間計算量が NlogN である非常に安定した並べ替え方法です。

マージソートの 2 つのステップ

1. 最初に分割し、番号が 1 つだけになるまで分割します

2. その後、分割が完了します、再帰的マージを開始します。

#分割プロセス

#上の図からわかるように、マージします。 sort 配列を 2 つに分割し、数値が 1 つだけの場合は分割を停止します。

分割コードは非常に簡単です。中央を指すポインタ q を取得し、配列を (start, p) と (p, end) の 2 つの部分に分割します。

• p は配列の開始添字を表します。

• r は配列の終了添字を表します。

    function pide(p, r){
        return Math.floor( (p + r) / 2 );
    }

マージ プロセス

マージ プロセスは上の図に示すとおりです

1. トラバース 2データのセット

2. サイズを比較

##小さい値が取り出され、最初の位置に配置されます

3. ## 例:

配列 A のデータが [2,5,1,3]

• であると仮定します。分割すると (0,2),(2,4) になります;

• A.slice(0,2) と A.slice(2,4)= を通じて 2 つが得られます。 > 配列 A1[2,5] および A2[1,3]

• 次に、配列 [2,5,1,3] を走査します。両側の比較を取得します。小さい数値は 1、2 回目は 2、3 回目は 3、4 回目は 5

•     function merge(A, p, q, r){
          const A1 = A.slice(p, q);
          const A2 = A.slice(q, r);
          
          // 哨兵，往A1和A2里push一个最大值，比如防止A1里的数都比较小，导致第三次遍历某个数组里没有值
          
          A1.push(Number.MAX_SAFE_INTEGER);
          A2.push(Number.MAX_SAFE_INTEGER);
          // 循环做比较，每次取出较小的那个值
          for (let i = p, j = 0, k = 0; i メイン プログラム

メインプログラムは上記の操作を再帰的に繰り返すことです

    function merge_sort(A, p = 0, r) {
      r = r || A.length;
      if (r - p === 1) {
        return;
      }
      const q = pide(p, r);
      merge_sort(A, p, q);
      merge_sort(A, q, r);
      merge(A, p, q, r);
    
      return A;
    }

完全なコード

    function pide(p, r) {
      return Math.floor((p + r) / 2);
    }
    
    function merge(A, p, q, r) {
      const A1 = A.slice(p, q);
      const A2 = A.slice(q, r);
      A1.push(Number.MAX_SAFE_INTEGER);
      A2.push(Number.MAX_SAFE_INTEGER);
    
      for (let i = p, j = 0, k = 0; i <h3></h3>

以上がJavaScript でのマージソートの概要 (コード例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。