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

Edison 發(fā)布于2019-08-21 14:15 / 837人閱讀

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

基本思想

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

自頂向下的歸并排序

采用遞歸的方式，方法比較簡(jiǎn)潔

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

自底向上的歸并排序

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