时间复杂度 O(N*logN)：
归并排序，堆排序（大根堆，小根堆，heapInsert/heapify)，快速排序（荷兰国旗问题）。
归并排序
L — Mid — R
先让 左有序，右有序。
归并 谁小copy谁
def mergeSort(data):def mergeSortFunc(data, L, R):if L==R:return mid = L+(R-L)//2mergeSortFunc(data, L, mid) //左部分 merge sortmergeSortFunc(data, mid+1, R)//右部分 merge sortmerge(data, L, R, mid) // 左右 mergedef merge(data, L, R, M):help_arr = []p1 = Lp2 = M+1while p1<=M and p2<=R:if data[p1] <= data[p2]:help_arr.append(data[p1])p1++else:help_arr.append(data[p2])p2++while p1<=M:help_arr.extend(data[p1:M+1])while p2<R:help_arr.extend(data[p2:R+1])data[L:R+1] = help_arrif len(data) < 2:returnmergeSortFunc(data, 0, len(data)-1)
T(N) = 2T(N/2) +O(N) 所以 时间复杂度就是 O(N*logN)， 额外空间复杂度是 O(N)
题目：小和问题 和 逆序对问题
小和问题：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和，求一个数组的小和。
//解法: 暴利查询 每个数查询左侧比他小的值 并且求和， 时间复杂度O(N^2)//解法2： 归并。一个数a 左边比他小的数加和 产生小和 与 右边有多少个比他大产生 n*a 小和 等价.'''例： 1 3 4 2 5划分左右 1 3 42 5划分左右 1 3 4 2 5merge 时 右侧比 左侧大的时候 产生小和。1 3 merge：1<3 , 右侧有1个比1 大。所以 1* 113 4 merge: 1<4，右侧有1个比1大， 产生1*1, 3和4比较， 3<4，右侧有1个比3大，产生1*3.得到 1 3 4 2 5 merge: 2 < 5， 右侧有1个比2大，所以产生1*2得到2 5134 25 merge：--> 1 < 2： 右侧有2个比1大， 产生2*1. 新的数组得到 1. 原数组为 34 25--> 3 > 2: 不产生小和。新的数组为 1 2，原数组为 34 5--> 3 < 5: 右侧有1个比3大， 产生1*3. 新数组得到 1 2 3， 原数组为4 5--> 4 < 5: 右侧有1个比4大， 产生1*4. 新数组为 1 2 3 4 5. 最后产生的小和： 1*1 + 1*1 + 1*3 + 1*2 + 2*1 + 1*3 + 1*4 = 16merge 实质：让左侧的数 依次碰到每一个右侧的数。 每一次搞定的左侧 不需要重复求，并且计算右侧有多少个比当前数大的时候 可以通过下标直接计算得到 不需要一个个数，因为左侧和右侧都是有序的，当左侧小于右侧的时候 产生小和。 merge sort 好的地方在于 每次比较结果都是变成有序序列。后续比较 只需要左组 和右组进行比较，不需要组内比较， 只需要跨组比较。暴利查询：1： 左侧小于1的 无。 3： 左侧小于3的 1， 4： 左侧小于4的1，3，2： 左侧小于2的15： 左侧小于5的1，2,3,4 加和： 1+1+3+1+1+2+3+4 = 16'''def leastSum(data):def mergeSort(data, L, R):if L==R:return 0mid = L+(R-L)//2return mergeSort(data, L, mid) + mergeSort(data, mid+1, R) + mergeAndSum(data, L, R, mid)def mergeAndSum(data, L, R, Mid):p1 = Lp2 = Mid+1help_arr = []ret = 0while p1 <= Mid and p2 <= R:if data[p1]< data[p2]:help_arr.append(data[p1])ret += (R-p2+1)*data[p1]p1++else data[p1]>=data[p2]://相等的时候 copy 右部分。help_arr.append(data[p2])p2++while p1<=Mid:help_arr.extend(data[p1:Mid+1])while p2<=R:help_arr.extend(data[p2:R+1])data[L:R+1] = help_arrreturn ret//leastSum funcif len(data)<2：returnreturn mergeSort(data, 0, len(data)-1, ret)
逆序对：在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有的逆序对。（即求每个数 左边多少个比它大的数）
def reverseData(data):if len(data)< 2:returndef mergeSort
堆
堆：用数组实现的完全二叉树结构（默认下标从0开始）
0 1 2 3 4 5 6 7
–> 0
1 2
3 4 5 6
完全二叉树： 结点i, 父节点 (i-1)/2 左孩子： 2i +1， 右孩子： 2i+2
大根堆：对于每颗子树的最大值 就是 父节点
小根堆：对于每颗子树的最小值 就是父节点
heapsize 是堆的一个重要参数。
任何一个数组 都可以按照大根堆的方式进行排序。 时间复杂度为O(Log_2 N)
def heapInsert(data, index): //数字 来到了 index 位置，如何往上移动while data[index] > data[(index-1)//2]:data[index], data[(index-1)//2] = data[(index-1)//2],data[index]index = (index-1)//2// 即包含了index在0位置 没有父节点的时候 也包含 index在其他位置 有父节点的时候// index = 0 时， (index-1)//2 也等于0
如果用户跟我要数的时候，比如要大根堆的堆顶，但是剩下的还是希望是大根堆结构。如何做？
用最后一个位置填堆顶，heapsize 减1，相当于把最后一个位置在堆里面移除。此时需要调整为大根堆，也就是把堆顶往下调整。
时间复杂度为O(Log_2 N)
def heapify(data, index, heapSize):left = index * 2 + 1 //左孩子下标while left < heapSize： //下方还有孩子的时候if left+1 < heapSize and data[left+1] > data[left]:largest = left+1else:largest = leftif data[largest] < data[index]:largest = indexbreakdata[largest], data[index] = data[index], data[largest]index = largestleft = index*2 + 1
如果某个位置的值发生了变化，则可以heapInsert 和heapify 各来一遍，最多只可能发生一个函数操作。
堆排序
给定一个数组，先把数组整体变成大根堆，此时heapsize=N。
比如： 9 8 3 7 6 2 1
step-1: 建立大根堆
step-2:把堆顶 和最后一个位置交换。把最后一个位置去掉。heapSize-1
step-3: 调整当前的数组为大根堆。
如果数组放那边，调整成大根堆 可以自顶往上(时间复杂度为O(logN))，也可以自底往上（时间复杂度度O(N)）。
自底往上把数组调整成大根堆。一开始认为数组为一个完全二叉树，从最后一个数开始 调整为大根堆（看他是否比每一个子孩子大，如果是的话 就往下走）heapify
堆排序：时间复杂度为O(NlogN), 额外空间复杂度O(1)
//从顶往下def heapSort(data):if len(data)<2:returnfor i in range(0, len(data)):heapInsert(data[i],i)heapSize = len(data)-1data[0],data[heapSize] = data[heapSize],data[0]while heapSize>0:heapify(data,0,heapSize)data[0],data[heapSize] = data[heapSize],data[0]
堆扩展
已知一个几乎有序的数组，几乎有序是指的是 如果把数组排好顺序的话，每个元素一定的距离可以不超过K， 并且K相对于数组来说比较小。请选择一个合适的排序算法针对这个数组排序。
答： 使用堆。 为什么？
如何用？
先把0-（K+1）个数 设置为小根堆，也就是0位置放最小的。
然后再把1-（K+2）个数 设置为小根堆，得到1的位置。
。。。
时间复杂度O(N * log K) (小根堆调整是log K 级别的)
快速排序
5-1：快排的partition的思想
问题1： 给定一个数a，和数组A，请先做到 把小于等于a的放到左边，大于a的放到右边。要求时间复杂度O(N)，额外空间复杂度O(1)。
方法：
设一个小于等于 区域。最开始为空。
当前数 <= a, 当前数和小于等于区域下一个数 交换，然后小于等于区域阔一个位置，当前数跳到下一个。
当前数 >a, 当前数直接跳下一个。
需要有的参数：小于等于区域指针，当前数指针。
问题1拓展：荷兰国旗问题。小于a的放到左边，等于a放中间，大于a的放右边。
方法：
当前数=划分值， 当前数跳到下一个
当前数<划分值，当前数 与小于区域 下一个数 交换，小于区域 往后扩一个，当前数跳到下一个
当前数>划分值，当前数与大于区域 前一个数 交换，大于区域往前扩一个，当前不变。
当前数与大于区域撞上时，停止。
小于划分值区域 等于区域 当前数 …（待定区域） 大于区域
def NetherLandsFlag(data,p):def partition(data, L, R, p):// p是划分值，要把L-R区间调整less = L-1 //小于区域的右边界more = R + 1//大于区域的左边界while L< more： // L是当前数下标if data[L] < p：//小于划分值data[L], data[less+1] = data[less+1], data[L]//交换less++L++else if data[L]> p：data[L], data[more-1] = data[more-1], data[L]more--else:L++return [less+1, more-1] //等于区域的下标if len(data)<1:returnpartition(data, 0, len(data)-1, p)
5-2：快排
不改进的快速排序：
1) 把数组范围中的最后一个数作为划分值，然后把数组通过荷兰国旗问题分成3个部分：左侧<划分值，中间==划分值，右侧>划分值。
2)对左侧范围和右侧范围，递归执行。
分析：
1）划分值越靠近两侧，复杂度越高，划分值越靠近中间，复杂度越低.
2）可以轻而易举地举出最差的例子，所以不改进的快排时间复杂度是O(N^2) （比如：1,2,3,4,5,6 划分值是6）。最好的情况是partition 的位置几乎在中点,时间复杂度O(NlogN)。
3）为了防止每次都是最差的情况出现，则通过L-R上随机选择一个数和N-1位置交换，这样降低复杂度。 (因为随机选择一个数，所以各种情况都是均等的，最后平均复杂度为O(NlogN))
经典快排：
(L-R上随机选一个数字和N-1位置上的数进行交换）X 在N-1位置上，对0-N-2上的数进行partition <=x, >x (<=x 左侧，>x 右侧，然后把x和>x区域的第一个数交换)，保证小于等于区域最后一个数是x.这样对于<=区域继续递归，然后对>x区域递归。 Base case: 区域只有一个值时 不需要排序。
（最差的情况 时间复杂度O(N^2)，空间复杂的O(N)，最好的情况是时间复杂度O(N*logN)，空间复杂度O(logN)）
改进的快排：
（L-R上随机选一个数字和N-1位置上的数进行交换）X是N-1上的划分值，在0 - (N-2)上进行荷兰国旗加速 <x， =x， >x（得到3个区域），然后把X和大于区域第一个值交换，并且大于区域往后移一位。然后在<x 和>x 区域分别做递归.
改进VS 经典快排：
改进的快排是每次排序 可以把所有等于x的都搞定 ，而经典的快排是每次都只能搞定一个数(也就是只有最后那个划分值 放到正确的位置)
def quickSort(data):def partition(data, L, R)://less = L-1more = R // 最后一个作为划分值while L < more:if data[L] < data[R]:data[L], data[less+1] = data[less+1],data[L]L++less++else if data[L] > data[R]:data[L], data[more-1] = data[more-1],data[L]more-- else:L++data[more-1], data[R] = data[R],data[more-1]return (less+1, more)def q_sort(data, L, R)://排好L-R之间的数if L<R:index = random(L, R)data[R], data[index] = data[index], data[R]p = partition(data, L, R)q_sort(data, L, p[0]-1)q_sort(data, p[1]+1, R)if len(data)<2:returnq_sort(data, 0, len(data)-1)
如果觉得《基础算法-2: 时间复杂度为O(N*logN)的排序算法》对你有帮助，请点赞、收藏，并留下你的观点哦！
