ホームページ >ウェブフロントエンド >jsチュートリアル >JavaScriptでのマージソートの詳しい説明

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

韦小宝オリジナル: 2018-03-14 14:14:201456ブラウズ

この記事では 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でのマージソートの詳しい説明

マージソートの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でのマージソートの詳しい説明

関連記事