1. 归并排序是第一个可以实际使用的排序算法。其复杂度为 O(n_log(_n))。
  2. 归并排序是一种分而治之算法。其思想是将原始数组切分成较小的数组，直到每个小数组只

有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

描述

  • 把长度为n的输入序列分成两个长度为n/2的子序列；
  • 对这两个子序列分别采用归并排序；
  • 将两个排序好的子序列合并成一个最终的排序序列。

代码实现及说明

  • 由于是分治法，归并排序也是递归的。我们要将算法分为两个函数：第一个负责将一个大数

组分为多个小数组并调用用来排序的辅助函数。这里声明的主要函数。

  1. const mergeSort = (arr, compareFn) => {
  2.   const length = arr.length;
  3.   if (length > 1) {
  4.     const middle = Math.floor(length / 2);
  5.     const left = mergeSort(arr.slice(0, middle), compareFn);
  6.     const right = mergeSort(arr.slice(middle, length), compareFn);
  7.     return merge(left, right, compareFn);
  8.   } else {
  9.     return arr;
  10.   }
  11. }

说明：(复习时补充说明)

  • merge函数负责合并和排序小数组来产生大数组，直到回到原始数组并已排序完成。

    1. const merge = (left, right, compareFn) => {
    2. let i = 0;
    3. let j = 0;
    4. const result = [];
    5. while (i < left.length && j < right.length) {
    6.   result.push(
    7.     compareFn(left[i], right[j]) ? left[i++] : right[j++]
    8.   );
    9. }
    10. return result.concat(i < left.length ? left.slice(i) : right.slice(j));
    11. }

    说明：(复习时补充说明)

  • 最终测试代码 ```javascript const arr = [23,34,1,4,7,64,543,123,6,2,12,36];

const compareFn = (a, b) => { return a < b; }

const merge = (left, right, compareFn) => { let i = 0; let j = 0; const result = []; while (i < left.length && j < right.length) { result.push( compareFn(left[i], right[j]) ? left[i++] : right[j++] ); } return result.concat(i < left.length ? left.slice(i) : right.slice(j)); }

const mergeSort = (arr, compareFn) => { const length = arr.length; if (length > 1) { // 将长度大于1的数组拆分为左右两个数组 const middle = Math.floor(length / 2); // 递归拆分 const left = mergeSort(arr.slice(0, middle), compareFn); const right = mergeSort(arr.slice(middle, length), compareFn); // 排序并组合左右数组 return merge(left, right, compareFn); } else { return arr; } }

mergeSort(arr, compareFn); ```

图示

image.png