ホームページ >ウェブフロントエンド >jsチュートリアル >JavaScript でのマージソートの概要 (コード例)

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

不言
不言転載
2019-01-10 09:47:192205ブラウズ
この記事では、JavaScript でのマージ並べ替えの概要 (コード例) を紹介します。必要な方は参考にしていただければ幸いです。

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

マージ ソート

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

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

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

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

#分割プロセス

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

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

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

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

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

    function pide(p, r){
        return Math.floor( (p + r) / 2 );
    }
マージ プロセス

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

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

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

  2. サイズを比較

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

配列 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 サイトの他の関連記事を参照してください。

声明:
この記事はsegmentfault.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。