排序- 归并排序

简介

前面三种排序算法只有教学价值，因为效率低，很少实际使用。归并排序（Merge sort）则是一种被广泛使用的排序方法。

基本思想💡

将两个已经排序的数组合并，要比从头开始排序所有元素来得快。因此，可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。

提示💡

依次两两比较两组元素，将小的放入结果数组。

算法实现

Javascript 简洁实现(推荐)

let mergeSort = (arr) => {
  if (arr.length < 2) return arr;
  let middle = parseInt(arr.length / 2),
  left = arr.slice(0, middle),
  right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}
let merge = (left, right) => {
  let result = [];
  while (left.length && right.length) {
    left[0] <= right[0] ?
    result.push(left.shift()) :
    result.push(right.shift());
  }
  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());
  return result;
}

阮一峰Javascript实现

• 合并函数

function merge(left, right){
    var result  = [],
        il      = 0,
        ir      = 0;
 
    while (il < left.length && ir < right.length){
        if (left[il] < right[ir]){
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }
 
    return result.concat(left.slice(il)).concat(right.slice(ir));
}

上面的 merge 函数，合并两个已经按升序排好序的数组。首先，比较两个数组的第一个元素，将其中较小的一个放入 result 数组；然后，将其中较大的一个与另一个数组的第二个元素进行比较，再将其中较小的一个放入 result 数组的第二个位置。以此类推，直到一个数组的所有元素都进入 result 数组为止，再将另一个数组剩下的元素接着 result 数组后面返回（使用 concat 方法）。

有了 merge 函数，就可以对任意数组排序了。基本方法是将数组不断地拆成两半，直到每一半只包含零个元素或一个元素为止，然后就用 merge 函数，将拆成两半的数组不断合并，直到合并成一整个排序完成的数组。

function mergeSort(myArray){
 
    if (myArray.length < 2) {
        return myArray;
    }
 
    var middle = Math.floor(myArray.length / 2),
        left    = myArray.slice(0, middle),
        right   = myArray.slice(middle);
 
    return merge(mergeSort(left), mergeSort(right));
}

上面的代码有一个问题，就是返回的是一个全新的数组，会多占用空间。因此，修改上面的函数，使之在原地排序，不多占用空间。

function mergeSort(myArray){
 
    if (myArray.length < 2) {
        return myArray;
    }
 
    var middle = Math.floor(myArray.length / 2),
        left    = myArray.slice(0, middle),
        right   = myArray.slice(middle),
        params = merge(mergeSort(left), mergeSort(right));
    
    // 在返回的数组头部，添加两个元素，第一个是0，第二个是返回的数组长度
    params.unshift(0, myArray.length);
 
	// splice用来替换数组元素，它接受多个参数，
	// 第一个是开始替换的位置，第二个是需要替换的个数，后面就是所有新加入的元素。
	// 因为splice不接受数组作为参数，所以采用apply的写法。
	// 这一句的意思就是原来的myArray数组替换成排序后的myArray
    myArray.splice.apply(myArray, params);
 
	// 返回排序后的数组
    return myArray;
}

ES6 实现

/**
 * 归并排序：先分后合
 * @param {*} arr
 * @returns
 */
function mergeSort(arr) {
  if (arr.length < 2) return arr;
  let midddle = parseInt(arr.length / 2);
  const left = arr.slice(0, midddle);
  const right = arr.slice(midddle);
  return merge(mergeSort(left), mergeSort(right));
}
const merge = (left, right) => {
  let result = [];
  //两两比较数组开头元素
  while (left.length && right.length) {
    left[0] <= right[0]
      ? result.push(left.shift())
      : result.push(right.shift());
  }
  // 将剩余元素放入结果中
  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());
  return result;
};

测试代码

let arr = [1, 5, 4, 3, 6, 8];
console.log("原数组", arr);
arr3 = mergeSort(arr);
console.log("归并排序：", arr);

效果演示

扩展阅读

• 说说你对分而治之、动态规划的理解！区别！