2. 认识O(NlogN)排序

Tags: 递归, 排序算法

归并排序 （Merge Sort）

• 使用递归实现的排序
• 时间复杂度为$O(NlogN)$（对应的Master公式中，$a=2,b=2,d=1$）
• 空间复杂度是$O(N)$(即在下面的代码中开辟了 help 变量)
• 这个方法为什么能到$O(NlogN)$? (为什么$O(N^2)$和$O(N)$差?) 因为其浪费了大量的比较行为。即每一轮的比较都是独立的，每一轮比较的信息只用来决定了本轮的一个数的位置。而归并排序并没有浪费比较行为，这种比较行为的信息变成了一个有序的部分，这个部分是可以被下一轮利用上，因此能够达到$O(NlogN)$
• 步骤：求中点位置，先排左侧序，再排右侧序。之后Merge成整体使其有序。具体来说，在Merge的时候，可以开辟一个临时空间，左右侧指针从两区间左侧开始，哪个小拷贝哪个到临时变量中，之后移动指针，直到其中一个越界，然后直接拷贝另一个剩下的。 也可以说，让其整体有序的过程用了外排序，即借助外部数组排好序。
• 实际代码

递归行为中的Master公式

求解子问题规模相等的递归行为的时间复杂度的公式

$$T(N)=a\times T(\frac{N}{b})+O(N^d)$$

其中，$T(N)$表示母问题的规模是$N$，$T(\frac{N}{b})$表示子问题的规模为$\frac{N}{b}$（即子问题必须等规模），$a$表示调用子问题的次数，而$O(N^d)$表示除去子问题后，剩下的部分时间复杂度为$O(N^d)$ 而满足Master公式的递归，其时间复杂度为

$$\begin{array}{rl}\text{if}& lo{g}_{b}a<dO(N^d)\\ \text{if}& lo{g}_{b}a>dO(N^{lo{g}_{b}a})\\ \text{if}& lo{g}_{b}a=dO(N^{d}logN)\end{array}$$

举例：利用递归求解数组最大值

• 示例代码 关于上图中求中点的解释：如果使用mid=(L+R)/2来求重点，可能会导致溢出。因此可以写成mid=L+(R-L)/2，这样一定保证不会溢出。而上图中>>1（右移一位）就等同于其除以2了，而且直接右移一位比除2要快。

在本问题中，母问题的规模是$T(N)$，子问题的调用是相等的，是$T(\frac{N}{2})$,子问题调用了两次，除了子问题调用之外，剩下的语句复杂度是$O(1)$，即$a=2,b=2,d=0$,因此其Master公式为 $T(N)=2\times T(\frac{N}{2})+O(N^0)$

• 另外一个例子：如果上问题中 process 函数处理左侧2/3的最大值和右侧1/3，那么本问题就不满足Master公式，因为其子问题的规模不是相等的。

快排

1.0版本：先以最后一个数为标的排序，左侧为小于区域，右侧为大于区域，再将该标的和右侧区域第一个数字换位（可以肯定的是该标的值一定是在这里），以这里为分界，两边分别递归重复上述步骤。（有点像荷兰国旗的简化版，因为没有等于区域）

2.0版本：比快排1.0版本多一个等于区域，也同样交换标的和大于区域的第一个值，后以该等于区域边界为两边的界，重复递归。（和荷兰国旗问题设置和思路一致）

2.0版本相对1.0版本更快一点。两者的时间复杂度都是$O(N^2)$，最差的例子都是有序数组，最后的标的都是当前数组最大值.(划分值找的很不好就会造成最差情况，而划分值取到中点，就是$O(NlogN)$（最好情况）

3.0版本：标的值随机选，之后和最后位置的换，重复2.0版本。

3.0版本引入随机，而随机就会涉及到概率（即无法人为构建最差例子了，而1.0和2.0可以），无论是找到最好还是最差或者其他，他们都是等概率的，这样就会降低其时间复杂，其时间复杂度的计算为长期期望。其时间复杂度为$O(NlogN)$。
其空间复杂度也是$O(logN)$级别的，计算也是涉及到了概率累加（对于递归的，要看递归最多能加到几层）

实际代码：

相关题目

• 小和问题 递归
  • 题目: 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。比如数组[1,3,4,2,5]的小和为16。请写出计算任意数组的小和的函数。
  • 解法：
    • 思路：可以是MergeSort的深度改写。比如[1,3,4,2,5]，1右边有多少个数比1大，就会产生多少个1的小和，显然，会产生4个1、2个3、1个4、1个2的小和，然后相加。其实就当于拆开来求了。但是要注意当左右组相等的时候，要首先拷贝右组的，否则不能很快知道右侧当前的小和。
    • 解法1：暴力求解，$O(N^2)$
    • 解法2：按照思路来写，就是按照MergeSort的思路排好序后，即完成了小和的计算。
      • 

• 求逆序对 递归
  • 题目：在一个数组中，左边的数字如果比右边的数字大，则这两个数字构成一个逆序对，请找到逆序对的数量。如[3,2,4,5,0]，共有5个逆序对。
  • 题解：跟上题一样，只不过上面是左边小，这个是左边大。
• 荷兰国旗问题 双指针
  • 题目：给定数组arr和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度为$O(1)$，时间复杂度为$O(N)$。
  • 思路：首先注意到这里没有要求每一块都是有序的。从左右两边开始，设设置两个指针分别是指示左区域（小于区域）和右区域（大于区域），另设一个当前指针。当当前指针的数字小于num，和小于区域的下一个数交换，右扩小于区域，当前指针走下一个；若当前指针=num，当前指针走下一个；若当前指针>num，当前指针和大于区域前一个值互换，当前指针不变。当当前指针和右侧区域重合，结束。相当于小于区域推着等于区域往前走，当和大于区域撞上了，就结束。