JavaScript中歸併排序詳解

本篇文章講述了JavaScript中歸併排序，大家對JavaScript中歸併排序不了解的話或對JavaScript中歸併排序感興趣的話那麼我們就一起來看看本篇文章吧， 好了廢話少說進入正題吧

JavaScript中歸併排序

#作為一種典型的分而治之思想的演算法應用，歸併排序的實作由兩種方法：

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中文網其他相關文章！