认识O(NlogN)的排序

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)