ホームページ >ウェブフロントエンド >jsチュートリアル >JavaScript でのマージソートの概要 (コード例)
マージ ソート (MERGE-SORT) は、分割統治法 (pide) を使用するマージ操作に基づく効果的な並べ替えアルゴリズムです。 andConquer) は非常に典型的なアプリケーションです。すでに順序付けされているサブシーケンスをマージして、完全に順序付けされたシーケンスを取得します。つまり、まず各サブシーケンスを順序どおりにしてから、サブシーケンス セグメントを順序どおりにします。 2 つの順序付きリストが 1 つの順序付きリストにマージされる場合、それは双方向マージと呼ばれます。
マージ ソートは、平均、最良、最悪にかかわらず、時間計算量が NlogN である非常に安定した並べ替え方法です。
最初に分割し、番号が 1 つだけになるまで分割します
その後、分割が完了します、再帰的マージを開始します。
#上の図からわかるように、マージします。 sort 配列を 2 つに分割し、数値が 1 つだけの場合は分割を停止します。
分割コードは非常に簡単です。中央を指すポインタ q を取得し、配列を (start, p) と (p, end) の 2 つの部分に分割します。
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和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 サイトの他の関連記事を参照してください。