内容
- 荷兰国旗问题
- 改善后的经典快排序
- 随机快排
- 堆结构
- 堆排序
一.荷兰国旗问题
题目：
给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)
解决思想：
partition过程：
有一个数组，L~R。初始的时候，less = L-1，more = R+1，cur 是当前数组的值。
L~less表示小于num区域（当less初始为L-1时，意味着这个区域还不存在）
more~R表示大于num区域（当more初始为R+1时，意味着这个区域还不存在）
less~more区域为等于num区域
处理规则:
- cur < num， 把数组中当前位置和小于区域下一个数进行交换，小于区域扩一下
- cur = num， cur直接跳下一个
- cur > num, 当前位置和大于区域的前一个位置交换，然后考察换过来的数cur(>num/=num/<num)
- 如果cur = more时，停止
二.改善的经典快排
思想：
用待排数组的最后一个位置的数字x做划分，划分为小于x,等于x,大于x三个区域，然后等于区域不动，继续用左部分小于x区域和右部分大于x区域两部分做如上的划分，递归这个过程。
改善的经典快排存在的问题:
时间复杂度与数据状况有关
如：
最差的情况：等于区域打偏，如：待排数组为 1 2 3 4 5 6 7
每次partition的过程只搞定一个数，partition一次的时间复杂度时O(N),那么这种情况下的时间复杂度为O(N^2)。
最好的情况：等于区域正好在中间。那么根据master公式
T(N) = 2T(N/2)+O(N) （整个问题被分为两个同等规模的子过程，然后还有一个partition过程）
由于经典快排与数据状况有关。为了解决这种问题，有两种常规的规避数据状况的手段 1)随机 2)哈希
三.随机快排:
随机选择数组中的一个数与数组的最后一个数做交换，然后用随机选择的数做划分，这样最好的数据状况和最坏的数据状况都是一个概率事件。
时间复杂度是O(NlogN)，额外空间复杂度O(logN)
(只有随机快排是这样，最好是O(N),最差是O(NlogN),最差和最好是一个概率事件，期望是O(logN)。原因在于需要记录每次partition之后的断点位置)
工程上:
工程上常用随机快排，因为随机快排一次能搞定中间等于区域很多数，常数项比较低
工程上的随机快排是非递归行为,需要自己把递归行为改成非递归行为。
四.堆结构
完全二叉树:
堆就是一棵完全二叉树
- 满二叉树
- 从左到右依次补齐
引入:给定一个数组，可以在逻辑上产生与之对应的二叉树
逻辑对应关系:
给定位置 i ,左孩子在数组中的位置是2i + 1，右孩子在数组中的位置是2i + 2
给定一个孩子节点的位置为j，那么这个孩子节点对应的父节点位置为(j - 1)/2
因此，数组和一棵完全二叉树的关系是一一对应的。
堆结构
1)大根堆：任何一棵子树的最大值是子树的头部
2)小根堆: 任何一棵字数的最小值是字数的头部
数组对应的堆不一定是一个大根堆，那么如何调整成大根堆呢？
思想:
0~i的位置已经是一个大根堆了，新加入的一个节点，重新调整成大根堆。直到把整个数组对应的原始的堆调节成一个大根堆
新加入的节点，根据数组和堆对应的逻辑关系，找到自己的父节点，与父节点位置的数进行比较，如果大于父节点，则向上调整，否则不调整。重复这个过程。那么时间复杂度log1+log2+log3+... = O(N)
heapInsert过程(加堆过程)
经历一个新节点加入堆里面同时向上调整的过程
heapify过程
建立好的大根堆中的某个值变小，需要重新调整成大根堆。那么根据逻辑关系，找到变小的这个值的孩子节点，找到两个孩子中最大的那个与之比较，如果小于孩子节点，则与孩子节点进行交换，逐渐向下调整
减堆过程（弹出堆顶）
把堆顶位置的元素和堆的最后一个位置互换，然后heapsize--（heapsize是已经形成的堆的大小）,重新调整成大根堆
加堆和减堆的时间复杂度
都只与堆的层数有关，只需要在需要变化的路径上进行调整。与其他部分无关。因此一个元素加堆或者减堆时间复杂度为O(logN)。
优先级队列结构实际就是堆结构
五.堆排序
过程
1)首先把待排的数组调节成一个大根堆
2)将堆的最后一个位置和堆顶元素交换，heapsize--,进行减堆操作
3)0~heapsize范围内做heapify操作，重新调整成一个大根堆
4)repeat step 2 until heapsize = 0
思想:
相当于每次找头部，因为头部是当前堆最大的，找到一个最大的头部，再找次大的头部
时间复杂度
堆排序的时间复杂度，主要在初始化堆过程和每次选取最大数后重新建堆的过程
初始化建堆过程时间：O(n)
更改堆元素后重建堆时间：O(nlogn)
额外空间复杂度
O(1)
一、冒泡排序
每一轮相邻位置比较，判断交换与否，找到该轮最大/最小，放到相应位置，执行下一轮。
二、选择排序
每次找最大、最小放到相应位置。
三、插入排序
每次判断一个数跟前边所有的值得大小，找到合适位置，插入。
四、归并排序
分最多的组，两两合并，使组越来越小，每次合并按照目的顺序合并。关键在组的合并函数（为两个组设置标志，移动标志位去判断该让哪一个数进新组）
五、快速排序
随机选择某数，按该数分成左右两组。对左右两组再进行以上划分。
六、堆排序
建堆过程从n/2位置向前每一位进行与左右孩子的比较与交换。将堆顶与最后一个值交换，出最大值。堆调整，从堆顶（此时为不符合的情况）一直往下交换至大于/小于子节点为止，调整结束。
七、希尔排序
插排改良
插排往前比较一位。希尔而是一个设置步长。步长降低，直到步长为一。
八、桶排序
计数排序、基数排序。
时间复杂度：
一二三 ：N方
四五六七： N*logN
八 ：N
复杂度：
o（1）：一二三六七
o（logN）-0（N）:五
o（N） 四
o（M）八 （桶的数量）
稳定性（待排序中相同元素的相对次序是否改变）：
稳定： 一三四八
不稳定：二五六七
快排为啥叫快排：
不是说优良，而是在最好情况下，它的渐进复杂度与堆排序和归并排序相同，只是快速排序的常量系数比较小。
工程上排序是综合排序。
数组小，插排
数组大，快排或者o（N*logN）的排序。
总结：
一般来说，当数组长度小于60时，插排的时间复杂度为O(N^2),常数项较低，直接用插排
当数组长度较大时，若数据为基础类型，则使用快排，若数据为自定义类型，由于稳定性较好，使用归并排序
快速排序本身不能做到稳定，01 stable sort 很难，是超纲问题
比较器：用哪种方法进行比较
桶排序：一种数据状况出现的次数
工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序
1， 非基于比较的排序， 与被排序的样本的实际数据状况很有关系， 所
以实际中并不经常使用
2， 时间复杂度O(N)， 额外空间复杂度O(N)
3， 稳定的排序
题目：给定一个数组， 求如果排序之后， 相邻两数的最大差值， 要求时
间复杂度O(N)， 且要求不能用非基于比较的排序。
思路：
如果用排序法实现，其时间复杂度为O(NlogN)，而如果利用桶排序的思想（不是桶排序），可以做到O(N)，额外空间复杂度为O(N)。遍历arr找到最大值max和最小值min。如果arr的长度为N，准备N+1个桶，把max单独放在第N+1个桶中，[min,max)范围上的数放在1~N号桶里，对于1~N号桶中的每一个桶来说，负责的区间为(max-min)/N。如果一个数为num，它应该分配进(num-min)*len/(max-min)。
arr一共有N个数，旻、一定会放进1号桶中，max一定会放进最后的桶中，所以，如果把所有的数放进N+1个桶中，必然有桶是空的。产生最大差值的相邻数来自不同桶。所以只要计算桶之间数的间距可以，也就是只用记录每个桶的最大值和最小值，最大差值只可能来自某个非空桶的最小值减去前一个非空桶的最大值。