归并排序思考记录与代码实现 --- 图画的真累-526互联

归并排序
- 把数组不断从中间拆分，然后对前后两段分别排序，再将排好序的两部分合并在一起如下图数组排序。—— 分治思想：把大问题分解为小问题来解决，这通常会用到递归。
- 由代码可知，归并排序就是将数组不断地从中间切开，然后对每份切开的前后排进行排序
- - 两种不用额外空间的算法，在最坏时间复杂度上升到了O(n^2)，在空间复杂度上降低到了O(1)。
    - 第一种方式的思想，merge里的两组数据有一个前提：两组数据都是有序的。因此将前排的每项元素与后排的项比较，若前排元素＞后排元素，则发生交换，再对后排元素执行冒泡排序。之后前排指针前进一位，再与后排各项比较，循环直到前排的元素被轮完。需要注意的是：发生交换时，后排从交换位开始执行冒泡即可（因为后排交换过来的元素必然比交换点前的的元素大，不然前面就会执行交换）。
      - 由图上可发现另一个优化处：鉴于前后两排各自有序，那么当前排元素小于等于后排某元素时，该后排元素之后的元素就不必再与该前排元素进行比较（肯定比后面的小啊！...画图时看出来的，代码就不再改了）
    - 第二种方式的思想，通过两个指针，分别指向前排的队首和后排的队首。当且仅当后排指针不超过队尾且前排指针不超过后排指针（重合也不行）时，对前后排指针所指的元素进行比较。若前排元素＞后排元素，则将【前排指针位置，后排指针位置）之间的元素依次向后移一位，再将事先保存好的后排指针所指元素放在前排指针所指的位置上，之后前后排指针各自+1；前排元素≤后排元素，则只把前排指针+1。
      - 目前没脑子想有什么不对的或可以优化的，有想法请不吝赐教。
- 执行效率
  - 递归的时间复杂度也可以用递归来计算：假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式可推导出为：T(n) = 2^kT(n/2^k)+kn（推导公式如图）。当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 k=log2n 。我们将 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。
  - - 从我们的原理分析和伪代码可以看出，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好、最坏，还是平均情况，归并排序/递归的时间复杂度都是 O(nlogn)。
  - 最坏情况、平均时间复杂度同最好情况，为O(n^2)。
- 内存消耗：代码可见，不需要额外的存储空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。
- 稳定性：稳不稳定取决于将两个有序子数组合并成一个有序数组的代码。如果总是将相同元素位于原数组中较靠前的先放入合并后的数组，那它将是稳定的。