归并排序

本来是要探究多路归并的最优解的，却无意间碰到了归并排序，那就深入了解一下吧。

先来了解一下什么是分治法。

大体思路

将集合看作是 n 个长度为 1 的有序子表

两两归并，得到 n/2 个长度为 2 的子表

叶子结点即是数据的初态，根节点为排序之后的结果。由于分治法的实现应用常常以递归的形式出现，结合递归也是操作树结构最经典方式，由此可见递归没跑了。

递归一般由两个步骤组成：

递进过程

回归过程

由于我们的排序是自下而上进行归并排序的，可以得出对原数据的切分，应该是处于递进的过程，也就是整个递归栈被构建的过程。而核心排序应该是位于调用栈里每一个函数帧在弹栈时，对上一帧后续代码的执行中。这里应该再来一张图来描述递进的过程中将每一个数据切分到叶子节点上的示例。
温馨提示：大脑中应当正确地模拟栈的整个操作，有注意理解函数的执行过程

Code Time

function mergeSort(arr, first, last) { // 构建递归结构
  if(last - first < 1) { // 递进结束，已经到叶子节点，开始弹栈回归
    return
  }
  let middle = Math.floor((first + last) / 2)
  mergeSort(arr, first, middle) // 开始构建递归树
  mergeSort(arr, middle + 1, last)
  
  sortCurArr(arr, first, last, middle) // 当前节点的子树执行完毕弹栈后，开始排序当前 first~last 的子数组
}

/**
 * 对当前范围的元素开始排序
 * 由于是递归回归过程中调用的部分，因此可以得出 middle 左右两侧的数据都是有序的，
 * 因为插入排序对于相对有序的数据集来说效率是最高的，因此我们采用了改进后的插入排序
 */
function sortCurArr(arr, first, last, middle) {
  let tmp // 插入排序的辅助变量
  while(middle >= first && middle + 1<= last) { // 终止条件为
    if(arr[middle+1] <= arr[first]) {
      tmp = arr[middle + 1] // 临时取出要插入的元素
      for(let i = middle; i >= first; i--) { // 并将从要插入的位置开始到当前临界位置的元素一律后移，并插入
        arr[i+1] = arr[i]
      }
      arr[first] = tmp
      middle++
    } else {
      first++
    }
  }
}

改进后的插入排序：
正常的插入排序是从数据集第二个元素开始向前方合适的位置插入，时间复杂度计算方式为阶乘，值为 O(n^2)。
这里不同的是，我们以 middle 之前的部分作为被插入的集合，之后的部分作为插入排序中无序的部分（实际上是有序的）。插入一次后，middle++ 可以理解，优化的部分就在于对 first 的自增，由于我们知道后半部分实际上是有序的，因此在我们得知要插入的元素大于前方有序集合中的 某元素 时，可以推断出要插入的该元素后方的元素也同样大于前方有序的 某元素, 因此 某元素 及其之前的部分就可以从对比的范围中剔除掉了。

小谈

起初让我不解的部分是：一般回归中操作数据，都会以返回数据值的方式来与弹栈之后的栈顶函数进行通信连接，这里并没有取递归的结果，更没有返回，只是以 return 结束递进。后来发现，递进的过程中，每次都使用的是原数组，而 sortCurArr 则是直接操作原数组，调用栈里每一帧作用域中的输入数组 —— 有序子表 都是以原数组加上 first 和 last 进行标记生成的虚拟数组，因此函数调用结束后，只是将原数组的局部进行了重排。

参考：

常见排序算法 - 归并排序 (Merge Sort)

大体思路

Code Time

小谈

参考：

内容目录