成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

JavaScript排序算法（二）——?dú)w并排序

Edison / 835人閱讀

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

基本思想

一個分治的策略，先進(jìn)行劃分，然后再進(jìn)行合并
空間復(fù)雜度：nLogn

自頂向下的歸并排序

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

function mergeSort(arr){
  // 設(shè)置終止的條件，
  if (arr.length < 2) {
    return arr;
  }
  //設(shè)立中間值
  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進(jìn)result數(shù)組里
       result.push(left.shift());
    }else{
      //把right的右子樹推出一個，然后push進(jìn)result數(shù)組里
     result.push(right.shift());
    }
  }
  //經(jīng)過上面一次循環(huán)，只能左子列或右子列一個不為空，或者都為空
  while (left.length){
    result.push(left.shift());
  } 
  while (right.length){
    result.push(right.shift());
  }
  return result;
}
// 測試數(shù)據(jù)
var nums=[6,10,1,9,4,8,2,7,3,5]；
mergeSort(nums);
自底向上的歸并排序

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

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


Sorting Algorithms in Javascript


《Data Structures& Algorithms with JavaScript》Michael McMilan著

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/87832.html

相關(guān)文章

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

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

    haitiancoder 評論0 收藏0

  • JavaScript 排序算法圖解（JavaScript sorting algorithms）

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

    h9911 評論0 收藏0

  • JS數(shù)據(jù)結(jié)構(gòu)與算法_排序和搜索算法

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

    姘擱『 評論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

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

    zhou_you 評論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

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

    caoym 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<