2 Javascriptのソートアルゴリズム例 マージソート(マージソート)_基礎知識

マージ ソートは、マージ操作に基づく効果的な並べ替えアルゴリズムです。このアルゴリズムは、分割統治法 (Divide and Conquer) を使用する非常に典型的なアプリケーションです。

マージソート方法は、2 つ (またはそれ以上) の順序付きリストを新しい順序付きリストにマージすることです。つまり、ソートされるシーケンスがいくつかのサブシーケンスに分割され、各サブシーケンスが順序付けされます。次に、順序付けられたサブシーケンスを順序付けられたシーケンス全体にマージします。

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

マージ操作のプロセスは次のとおりです:

1. サイズが 2 つのソートされたシーケンスの合計になるようにスペースを適用します。このスペースは、マージされたシーケンスを格納するために使用されます。
2. 2 つのポインターを設定します。その初期位置は 2 つのソートされたシーケンスです。開始位置
3. 2 つのポインターが指す要素を比較し、比較的小さい要素を選択してマージ スペースに配置し、ポインターを次の位置に移動します
4. 特定のポインターになるまで手順 3 を繰り返しますシーケンスの最後に到達します
5. 他のシーケンスの残りの要素をすべて、マージされたシーケンスの最後に直接コピーします

例 1:

コードをコピー コードは次のとおりです:

/**
* マージ操作 (merge) は、マージアルゴリズムとも呼ばれ、ソートされた 2 つのシーケンスを 1 つのシーケンスにマージする操作を指します。
* マージソートアルゴリズムはマージ操作に依存します。
*
* マージ操作のプロセスは次のとおりです。
*
* 1. サイズが 2 つのソートされたシーケンスの合計になるようにスペースを適用します。このスペースは、マージされたシーケンスを格納するために使用されます。 sequence
* 2. 2 つのポインターを設定します。初期位置は 2 つのソートされたシーケンスの開始位置です
* 3. 2 つのポインターが指す要素を比較し、比較的小さい要素を選択してマージに入れますスペースを入力し、ポインタを次の位置に移動します
* 4. ポインタがシーケンスの最後に到達するまで手順 3 を繰り返します
* 5. 他のシーケンスの残りの要素をすべて、マージされたシーケンスの最後に直接コピーします
*
*/

function mergeSort(items) {
if (items.length < 2) {
return items;
}

var middle = Math.floor(items.length / 2) ,
left = items.slice(0, middle),
right = items.slice(middle),
params = merge(mergeSort(left), mergeSort(right));

params.unshift(0, items.length);
items.splice.apply(items, params);

アイテムを返す;

function merge(left, right ) {
var result = [],
il = 0,
ir = 0;

while (il if ( left[il] < right[ir]) {
result.push(left[il]); > return result.concat(left.slice(il)) .concat(right.slice(ir) ); = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];

mergeSort(arr);



例 2:





コードをコピー

コードは次のとおりです: