1 归并排序
1. 整体就是一个简单递归，左边排好序、右边排好序、让其整体有序
2. 让其整体有序的过程里用了排外序方法（左右两个对比，将数值较小的放进外部的一个数组内，然后被调用的数据指针往下移一位，相等时默认取左边的数据，如果一侧的数组数据被提取完成，将剩下的数据全部保存到外部数组即可）
3. 利用master公式来求解时间复杂度
4. 归并排序的实质
时间复杂度O(N*logN), 额外空间复杂度O(N)
2 归并排序的扩展
小和问题和逆序对问题
小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例子：[1, 3, 4, 2, 5]
1左边比1小的数，没有；3左边比3小的数，1；4左边比4小的数，1、3；2左边比2小的数，1；5左边比5小的数，1、3、4、2；
所以小和为 1+1+3+1+1+3+4+2 = 16
计算过程同归并排序类似，不过是需要在排序的同时也要求小和，以及当左右两个数据相等时需要先将右方的数据复制到外序数组。
逆序对问题
在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序对。
3 荷兰国旗问题
问题一
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
问题二
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
4 不改进的快速排序
1. 把数组范围中的最后一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分；
左侧<划分值，中间==划分值，右侧>划分值
2. 对左侧范围和右侧范围，递归执行
分析
1. 划分值越靠近两侧，复杂度越高；划分值就越靠近中间，复杂度越低
2. 可以轻而易举的举出最差的例子，所以不改进的快速排序时间复杂度为O(N^2)
5 随机快速排序（改进的快速排序）
1.在数组范围中，等概率的选取一个数作为划分值，然后把数组通过荷兰国旗分体分成三个部分；
左侧<划分值，中间==划分值，右侧>划分值
2. 对左侧范围和右侧范围，递归执行
3. 时间复杂度为O(N*logN)