JavaScript排序算法（二）——歸并排序

Edison 發布于2019-08-21 14:15 / 833人閱讀

摘要：首先將數據集分解為一組只有一個元素的數組，然后通過創建一組左右子數組慢慢將它們合并起來，每次合并都保存一部分排好序的數據，最后這個數組排序完全。

基本思想

一個分治的策略，先進行劃分，然后再進行合并
空間復雜度：nLogn

自頂向下的歸并排序

采用遞歸的方式，方法比較簡潔

function mergeSort(arr){
  // 設置終止的條件，
  if (arr.length < 2) {
    return arr;
  }
  //設立中間值
  var middle = parseInt(arr.length / 2);
  //第1個和middle個之間為左子列
  var left = arr.slice(0, middle);
  //第middle+1到最后為右子列
  var right = arr.slice(middle);
  if(left=="undefined"&&right=="undefined"){
     return false;
  }
  return merge(mergeSort(left), mergeSort(right));
}

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

  while (left.length && right.length) {
    if(left[0] <= right[0]){
      //把left的左子樹推出一個，然后push進result數組里
       result.push(left.shift());
    }else{
      //把right的右子樹推出一個，然后push進result數組里
     result.push(right.shift());
    }
  }
  //經過上面一次循環，只能左子列或右子列一個不為空，或者都為空
  while (left.length){
    result.push(left.shift());
  } 
  while (right.length){
    result.push(right.shift());
  }
  return result;
}
// 測試數據
var nums=[6,10,1,9,4,8,2,7,3,5]；
mergeSort(nums);

自底向上的歸并排序

遞歸的深度太深，使用一種非遞歸的方式。首先將數據集分解為一組只有一個元素的數組，然后通過創建一組左右子數組慢慢將它們合并起來，
每次合并都保存一部分排好序的數據，最后這個數組排序完全。

function mergeSort(arr){
  if(arr.length<2){
    return;
  }
  //設置子序列的大小
  var step=1; 
  var left,right;
  while(step
參考資料

Sorting Algorithms in Javascript

《Data Structures& Algorithms with JavaScript》Michael McMilan著

云服務器 GPU云服務器歸并排序算法歸并排序二路歸并排序 java歸并排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/87832.html

JavaScript 數據結構與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此，快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 評論0 收藏0
JavaScript 排序算法圖解（JavaScript sorting algorithms）

摘要：基礎構造函數以下幾種排序算法做為方法放在構造函數里。代碼圖解選擇排序選擇排序算法是一種原址比較排序算法。它的性能通常比其他的復雜度為的排序算法要好。代碼劃分過程圖解排序沒有定義用哪個排序算法，所以瀏覽器廠商可以自行去實現算法。基礎構造函數以下幾種排序算法做為方法放在構造函數里。 function ArrayList () { var array = []; // 交換位置...

h9911 2019-08-21 12:04 評論0 收藏0
JS數據結構與算法_排序和搜索算法

摘要：上一篇數據結構與算法樹寫在前面這是學習數據結構與算法的最后一篇博客，也是在面試中常常會被問到的一部分內容排序和搜索。上一篇：JS數據結構與算法_樹寫在前面這是《學習JavaScript數據結構與算法》的最后一篇博客，也是在面試中常常會被問到的一部分內容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無心去深入研究排序相...

姘擱『 2019-08-23 16:26 評論0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

zhou_you 2019-08-16 10:34 評論0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。用一張圖概括歸并排序英語，或，是創建在歸并操作上的一種有效的排序算法，效率為。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

caoym 2019-07-31 10:56 評論0 收藏0