javascript高级排序算法之归并排序

上次讨论了javascript的快速排序，
快排：

1. 选择一个基准元素，将数据列表分成两个子序列；
2. 对数据列表进行重新排序，将所有小于基准值的元素放在基准值的前面，所有大于基准值的元素放在基准值的后面；
3. 分别对较小元素的子序列和较大元素的子序列重复步骤1和2。

快速排序是基于“分而治之”思想，还有一种排序算法和快速排序很像，都是基于“分而治之”

归并排序

归并排序是一种分治算法。其思想是将原始数据切分成为较小的数组，直到每一个小数组只有一个位置，这个过程叫做分治。接着将小数组归并成为较大的数组，直到最后只有一个排序完毕的大数组，这个过程是归并。由于是分治法，所以归并排序也是递归的。
归并分两步：

1. 分（分治,拆分）
2. 并（归并）

所以我们应该写一个分治的函数，再写一个归并的函数。在分治的函数中返回归并的函数时不断递归调用自身，完成分割，在返回至归并，直至数组排序完成。

function mergeSortSplit(array) {
    // 如果长度为1就不用拆分了(递归函数的停止条件)
    if (array.length == 1) {
        return array;
    }
    //选择中间值
    const mid = Math.floor(array.length / 2);
    // 提取下标0到mid-1的元素到左数组
    const left = array.slice(0, mid);
    // 提取下标mid到length-1的元素到右数组
    const right = array.slice(mid, array.length)
    // 调用归并方法，并递归拆分
    return merge(mergeSortSplit(left), mergeSortSplit(right))
}

归并方法

//归并
/*
merge是接收两个数组，并从每个数组的首项开始进行比较，小的元素放到左边，大的元素放到右边。
*/
function merge(left, right) {
  // result是存放归并后的数组的数组
  const result = [];
  // il是左边数组的下标，ir是右边数组的下标，它们都从0开始
  let il = 0;
  let ir = 0;
  // 循环比较
  while (il < left.length && ir < right.length) {
    /*
    如果左边的元素比右边的元素小，就将他放到result中，反之把右边   的放进result。直至有一个数组到头了，就会结束循环，将另一个数组添加到result 的后面。
    */
    if (left[il] < right[ir]) {
      result.push(left[il++]);
    } else {
      result.push(right[ir++]);
    }
  }
  while (il < left.length) {
    result.push(left[il++]);
  }
  while (ir < right.length) {
    result.push(right[ir++]);
  }
  // 这个函数返回的是一个归并好的一个数组
  return result;
}

最后对两个方法进行封装

arr = [5, 7, 6, 1, 4, 3, 2, 9, 10, 8]
function mergeSort(myArr) {
    //归并
    const merge = (left, right) => {

        const result = [];
        let il = 0;
        let ir = 0;
        while (il < left.length && ir < right.length) {
            if (left[il] < right[ir]) {
                result.push(left[il++]);
            } else {
                result.push(right[ir++]);
            }
        }
        while (il < left.length) {
            result.push(left[il++]);
        }
        while (ir < right.length) {
            result.push(right[ir++]);
        }
        console.log('result', result);
        return result;
    }

    //拆分
    const mergeSortSplit = (array) => {
        if (array.length == 1) {
            return array;
        }
        const mid = Math.floor(array.length / 2);
        const left = array.slice(0, mid);
        const right = array.slice(mid, array.length)
        console.log('left', left);
        console.log('right', right);
        return merge(mergeSortSplit(left), mergeSortSplit(right))
    }
    return mergeSortSplit(myArr);
}
console.log(arr);
console.log(mergeSort(arr));

我们看下输出，通过console观察代码的执行过程

看图中的标注

归并排序和快速排序的区别

快速排序和归并排序的原理都是基于“分而治之”思想，即首先把待排序的元素分成两组，然后分别对这两组排序，最后把两组结果合并起来。
它们的区别在于，进行的分组策略不同，后面的合并策略也不同。

归并排序的分组策略：假设待排序的元素存放在数组中，那么其把数组前面一半元素作为一组，后面一半作为另一组。
快速排序的分组策略：根据元素的值来分组，即大于某个值的元素放在一组，而小于的放在另外一组，该值称为基准。所以，对整个排序过程而言，基准值的挑选非常重要，如果选择不合适，太大或太小，那么所有元素都分在一组了。

总的来说，快速和归并排序，如果分组策略越简单，后面的合并策略就越复杂，因为快速排序在分组时，已经根据元素大小来分组了，而合并时，只需要把两个分组合并起来就行了，归并排序则需要对两个有序的数组根据大小合并。