javascript排序算法-归并排序

归并排序

 概念：归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

 

 时间复杂度： O(nlogn)

 

代码实现

 

var mergeSortRec = function (array) {
  var length = array.length;// {1}
  if (length === 1) {// {2}
    return array;
  }
  var mid = Math.floor(length / 2), //{3}首先得找到数组的中间位
    left = array.slice(0, mid),//{4}左边小数组
    right = array.slice(mid, length);//{5}右边小数组
  return merge(mergeSortRec(left), mergeSortRec(right));// {6}调用merge函数，它负责合并和排序小数组来产生大数组，直到回到原始数组并已排序完成
}

var merge = function(left, right) {
  var result = [], //需要声明归并过程要创建的新数组以及用来迭代两个数组（left和right数组）所需的两个变量
    il = 0,
    ir = 0;
  while (il < left.length && ir < right.length) {//迭代两个数组的过程中
    if (left[il] < right[ir]) {// 我们比较来自left数组的项是否比来自right数组的项小。
      result.push(left[il++]);// 将该项从left数组添加至归并结果数组，并递增迭代数组的控制变量
    } else {
      result.push(right[ir++]);// 从right数组添加项并递增相应的迭代数组的控制变量
    }
  }
  while (il < left.length) { // 将left数组所有剩余的项添加到归并数组中
    result.push(left[il++]);
  }
  while (ir < right.length) { // 将right数组所有剩余的项添加到归并数组中
    result.push(right[ir++])
  }
  return result;
}

console.log(mergeSortRec([89,78,9,6765,80,3,6]))

举例：[8,7,6,5,4,3,2,1]

mergeSortRec([8,7,6,5,4,3,2,1])
过程如下图，把大数组递归地分成小数组，再通过小数组排好序合并成大数组。