[排序]归并排序和逆序数详解

前言

在排序中，我们可能大部分更熟悉冒泡排序、快排之类。对归并排序可能比较陌生。然而事实上归并排序也是一种稳定的排序，时间复杂度为O(nlogn).

归并排序是基于分治进行归并的，有二路归并和多路归并.我们这里只讲二路归并并且日常用的基本是二路归并。并且归并排序的实现方式有递归形式和非递归形式。要注意其中的区分(思想上没有大的区别，只是划分上会有区分后面会对比)。

并且归并排序很重要的一个应用是求序列中的逆序数个数。当然逆序数也可以用树状数组完成，这里就不介绍了。

归并和快排都是基于分治算法的。分治算法其实应用挺多的，很多分治会用到递归，也有很多递归实现的算法是分治，但事实上分治和递归是两把事。分治就是分而治之。因为面对排序，如果不采用合理策略。每多一个数就会对整个整体带来巨大的影响。而分治就是将整个问题可以分解成相似的子问题。子问题的解决要远远高效于整个问题的解决，并且子问题的合并并不占用太大资源。

至于归并的思想是这样的：

对于分治过程你可能了解了，但是这个两两merge的过程其实是很重要的。首先我们直到的两个序列都是有序的。其实思想也很简单，假设两个串串为 3 5 7 8和2 6 9 10进行归并操作。我们需要借助一个额外的数组team[8]将两个串串有序存进去就行。而流程是这样的：

在这里插入图片描述

非递归的归并 正常归并的代码实现都是借助递归的。但是也有不借助递归的。大部分课本或者考试如果让你列归并的序列，那么默认就是非递归的，比如一个序列9,2,6,3,8,1,7,4,10,5序列的划分也是这样的。

递归的归并 在代码实现上的归并可能大部分都是递归的归并。并且递归和分治整在一起真的是很容易理解。递归可以将问题分解成子问题，而这恰恰是分治所需要的手段。而递归的一来一回过程的来(分治)回(归并)，一切都刚刚好。

而递归的思想和上面非递归肯定不同的，你可以想想非递归：我要考虑当前几个进行归并，每个开始的头坐标该怎么表示，还要考虑是否越界等等问题哈，写起来略麻烦。

而非递归它的过程就是局部—>整体的过程，而递归是整体—>局部—>整体的过程。 而递归实现的归并的思想：