归并排序.md

归并排序

算法思想

利用归并的思想实现的排序方法，该算法采用经典的分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

情况一 : 两个有序数列合并

就比如是这样，将 [4, 5, 7, 8] 和 [1, 2, 3, 6] 合并。合并的最终结果是 [1, 2, 3, 4, 5, 6, 7, 8]

定义一个最终显示的数组 temp = []，同时定义 i = 0 (从 arr1 = [4, 5, 7, 8]开始)，j = 0 (从 arr2 = [1, 2, 3, 6]开始), 从比较 arr1 和 arr2 数组中开始比较第一个数，谁小就先取谁，然后放入 temp 数组中

情况二 : 无序数组

比如说一个序列 : [12 ,23, 1, 44, 233, 10, 9, 8]。

我们先分成两段：[12 ,23, 1, 44] 和 [233, 10, 9, 8]

发现还能再分成 4 段：[12 ,23] 和 [1, 44] ------ [233, 10] 和 [9, 8]

再分成 8 段：[12] -- [23] --[1] -- [44] 和 [233] -- [10] -- [9] -- [8]

这时候开始把子序列进行排序合并，一个元素就是有序的。所以不用排序。

合并成 2 个一组排序得到：[12，23] ---- [1，44] --- [10，233] --- [8，9]

再合并成 4 个一组排序得到：[1，12，23，44] --- [8，9，10，233]

最后合并得到最终结果：[1，8，9，10，12，23，44，233]

代码

/**
 * @desc sort，目的是分，不断的分段，再调用merge去合
 */
function sort(arr, low, hight) {
  let middle = parseInt((low + hight) / 2);
  if (low < hight) {
    // 处理左边
    sort(arr, low, middle);
    // 处理右边
    sort(arr, middle + 1, hight);
    // 左右归并
    merge(arr, low, middle, hight);
  }
  return arr;
}

/**
 * @desc 合并两个数组
 */
function merge(arr, low, middle, hight) {
  let temp = [];
  let i = low, // 指针 i，从左边开始走
    j = middle + 1, // 指针 j，从右边开始走
    k = 0; // temp[k]，目的是为了存放数据

  // 找到最小值放在temp辅助数组中
  while (i <= middle && j <= hight) {
    if (arr[i] < arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }

  // 处理较长部分
  while (i <= middle) {
    temp[k++] = arr[i++];
  }
  while (j <= hight) {
    temp[k++] = arr[j++];
  }

  // 使用temp中的元素覆盖arr中元素
  for (let q = 0; q < temp.length; q++) {
    arr[q + low] = temp[q]; // low为传进来的值，这里是为了覆盖arr
  }
}

var arr = [3, 5, 2, 7, 4, 9, 8, 6, 1];
console.log(sort(arr, 0, arr.length - 1));

时间复杂度和空间复杂度

归并排序的效率是比较高的，设数列长为 N，将数列分开成小数列一共要 logN 步，每步都是一个合并有序数列的过程，时间复杂度可以记为 O(N)，故一共为 O(NlogN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在 O(NlogN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

时间复杂度无论是在最好情况下还是在最坏情况下均是 O(nlgn)

需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)