JavaScriptでのマージソートの詳しい説明

この記事では JavaScript のマージ ソートについて説明します。JavaScript のマージ ソートについて知らない場合、または JavaScript のマージ ソートに興味がある場合は、この記事を見てみましょう。

JavaScript でのマージソート

分割統治のアイデアの典型的なアルゴリズム適用として、マージソートは 2 つのメソッドで実装されます:

1. トップダウン再帰 (すべての再帰メソッドは反復で書き換えることができます) 2 番目の方法があります)

2. ボトムアップ反復

「データ構造とアルゴリズム JavaScript の説明」では、著者はボトムアップ反復法を示しています。しかし、再帰的方法について、著者は次のように考えます。

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。

正直、この文はよくわかりません。 JavaScript コンパイラのメモリが少なすぎて再帰が深すぎるため、メモリ オーバーフローが発生しやすいということでしょうか?誰かが私にアドバイスをくれることを願っています。

選択ソートと同様に、マージソートのパフォーマンスは入力データの影響を受けませんが、時間計算量が常に O(n log n) であるため、パフォーマンスは選択ソートよりもはるかに優れています。価格は追加のメモリ容量です。

マージソートアニメーションのデモ

マージソートのJavaScriptコードの実装:

function mergeSort(arr) {  //采用自上而下的递归方法  
   var len = arr.length;  
   if(len < 2) {  
       return arr;  
   }  
   var middle = Math.floor(len / 2),  
       left = arr.slice(0, middle),  
       right = arr.slice(middle);  
   return merge(mergeSort(left), mergeSort(right));}function merge(left, right){  
   var result = [];  
  
   while (left.length && right.length) {  
       if (left[0] <= right[0]) {  
           result.push(left.shift());  
       } else {  
           result.push(right.shift());  
       }  
   }  
  
   while (left.length)  
       result.push(left.shift());  
  
   while (right.length)  
       result.push(right.shift());  
  
   return result;}

上記がこの記事のすべての内容です。あまり詳しくない場合は、両方を自分で実装できます。マスターするのは簡単です！

関連する推奨事項:

JavaScript の興味深い質問: リンク リストのマージ ソート

JavaScript は、リンク リストの挿入ソートとリンク リストのマージ ソートを実装します

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