归并排序-nlogn-常用

前言

归并排序是可以实际使用的排序算法。你在本书中学到的前三个排序算法性能不好，但归并排序性能不错，其复杂度为O(nlog(n))。

JavaScript的Array类定义了一个sort函数（Array.prototype.sort）用以排序JavaScript数组（我们不必自己实现这个算法）。
ECMAScript没有定义用哪个排序算法，所以浏览器厂商可以自行去实现算法。

例如，Mozilla Firefox使用归并排序作为Array.prototype.sort的实现，而Chrome（V8引擎）使用了一个快速排序的变体
Mozilla/Firefox 使用了 MergeSort。此时的时间复杂度是 O (n log n)。
自 V8 v7.0 / Chrome 70 起， V8 使用 TimSort, Python的排序算法. Chrome 70 是2018年9月13日发布的。此时时间复杂度 O (n算法性能)

归并排序

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

由于是分治法，归并排序也是递归的。我们要将算法分为两个函数：第一个负责将一个大数组分为多个小数组并调用用来排序的辅助函数。

我们来看看在这里声明的主要函数。归并排序将一个大数组转化为多个小数组直到其中只有一个项。由于算法是递归的我们需要一个停止条件，在这里此条件是判断数组的长度是否为1（行{1}）。如果是，则直接返回这个长度为1的数组，因为它已排序了。

如果数组长度比1大，那么得将其分成小数组。为此，首先得找到数组的中间位（行{2}），找到后我们将数组分成两个小数组，分别叫作left（行{3}）和right（行{4}）。

left数组由索引0至中间索引的元素组成，而right数组由中间索引至原始数组最后一个位置的元素组成。

行{3}和行{4}将会对自身调用mainSort函数直到left数组和right数组的大小小于等于1。

下面的步骤是调用merge函数（行{6}），它负责合并和排序小数组来产生大数组，直到回到原始数组并已排序完成。

例子

第一次切割，将原数组划分为两个子数组 [52, 63, 14, 59, 68] 和 [35, 8, 67, 45, 99]。
递归地将每个子数组继续切割，直到每个子数组中只剩一个元素。

[52, 63, 14, 59, 68]：切割成 [52, 63] 和 [14, 59, 68]。
[52, 63, 14, 59, 68]：切割成 [52, 63] 和 [14, 59, 68]。

将相邻的子数组归并成一个有序数组。

将相邻的子数组归并成一个有序数组。
将相邻的子数组归并成一个有序数组。

将相邻的子数组归并成一个有序数组。 [14, 52, 59, 63, 68] 和 [8, 35, 45, 67, 99] 归并成有序数组 [8, 14, 35, 45, 52, 59, 63, 67, 68, 99]。

最终，归并排序得到了一个有序的数组 [8, 14, 35, 45, 52, 59, 63, 67, 68, 99]。

第四步是怎么归并的？

在第三步中，我们得到了两个有序数组 [14, 52, 59, 63, 68] 和 [8, 35, 45, 67, 99]。接下来，我们要将这两个有序数组归并成一个更大的有序数组。

归并的基本思想是，首先比较两个数组的第一个元素，将较小的元素放入结果数组中，然后将该元素所在的数组的指针向后移动一个位置，继续比较下一个元素，直到一个数组的所有元素都被放入结果数组中。最后，将另一个数组中剩余的所有元素依次放入结果数组中。

在这个例子中，我们可以依次比较两个有序数组的第一个元素，得到一个新的有序数组：

[14, 52, 59, 63, 68] 和 [8, 35, 45, 67, 99] 归并成 [8, 14, 35, 45, 52, 59, 63, 67, 68, 99]

具体步骤如下：

比较两个数组的第一个元素，得到较小的元素 14。
将元素 14 放入结果数组中，并将 14 所在的数组 [14, 52, 59, 63, 68] 的指针向后移动一个位置。
比较两个数组的第一个元素，得到较小的元素 8。
将元素 8 放入结果数组中，并将 8 所在的数组 [8, 35, 45, 67, 99] 的指针向后移动一个位置。
比较两个数组的第一个元素，得到较小的元素 35。
将元素 35 放入结果数组中，并将 35 所在的数组 [8, 35, 45, 67, 99] 的指针向后移动一个位置。

重复以上步骤，直到有一个数组中的所有元素都被放入结果数组中。

实现1

数组长度是否小于等于1，如果是则直接返回该数组。否则，将数组平均分成两个子数组，然后递归地对左右子数组进行归并排序。最后将排好序的左右子数组合并成一个有序数组，并返回该数组。在合并两个子数组的过程中，我们使用双指针法，分别从两个子数组的开头开始比较大小，每次将较小的元素加入新的数组中，直到其中一个子数组的元素全部被加入新的数组中，然后将另一个子数组中剩余的元素直接加入新的数组中即可。

function mergeSort(arr) {
  // 如果数组长度小于等于1，直接返回数组
  if (arr.length <= 1) {
    return arr;
  }

  // 将数组平均分成两个子数组
  const mid = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

  debugger
  console.log('leftArr:', leftArr)
  console.log('rightArr:', rightArr)

  // 递归地对左右子数组进行归并排序
  const sortedLeftArr = mergeSort(leftArr);
  const sortedRightArr = mergeSort(rightArr);
  console.log('========')

  // 将排好序的左右子数组合并成一个有序数组
  const mergedArr = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < sortedLeftArr.length && rightIndex < sortedRightArr.length) {
    if (sortedLeftArr[leftIndex] < sortedRightArr[rightIndex]) {
      mergedArr.push(sortedLeftArr[leftIndex]);
      leftIndex++;
    } else {
      mergedArr.push(sortedRightArr[rightIndex]);
      rightIndex++;
    }
  }

  const mergedArrReturn = mergedArr.concat(sortedLeftArr.slice(leftIndex)).concat(sortedRightArr.slice(rightIndex));
  console.log('mergedArrReturn:', mergedArrReturn)
  return mergedArrReturn;
}

// 测试代码
const arr = [52, 63, 14, 59, 68, 35, 8, 67, 45, 99];
console.log(mergeSort(arr)); // [8, 14, 35, 45, 52, 59, 63, 67, 68, 99]

实现2

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function 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]) === Compare.LESS_THAN ? left[i++] : right[j++]);
  }
  return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

function mergeSort(array, compareFn = defaultCompare) {
  if (array.length > 1) { // 1
    const { length } = array;
    const middle = Math.floor(length / 2); // 2
    const left = mergeSort(array.slice(0, middle), compareFn); // 3
    const right = mergeSort(array.slice(middle, length), compareFn); // 4
    array = merge(left, right, compareFn); // 5
  }
  return array;
}

const array = [52, 63, 14, 59, 68, 35, 8, 67, 45, 99];

console.log('array', array)
console.log('array', mergeSort(array))

前言​

归并排序​

例子​

第四步是怎么归并的？​

实现1​

实现2​

前言

归并排序

例子

第四步是怎么归并的？

实现1

实现2