排序算法小结

冒泡排序

略····

选择排序

1. 一个数组，从0~N-1选择最小的和0位置值交换；1~N-1选择最小的和1位置值交换；以此类推。每次都是选择最小的放在前面。

插入排序：

1. 0~i-1位置是排好的，对于新来的第i个数，相当于把这个数按大小插到原来排好的牌里，对于计算机来说，插进去的过程就是一路交换。这个i-1位置，是从0开始一直往后扩的，一直扩到数组最后一个，这样这个数组就排好了。
2. 整体为O（N^2）算法，但是和数据状况有关系。

3. 递归行为和递归时间复杂度的估算

   1. 递归函数就是系统在帮你压栈
   2. 估计递归行为复杂度的通式：T(N) = aT(n/b)+O(n^d)

归并排序(merge)

1. 递归
   
   1. 先左边有序，再右边有序，再外排。外排就是准备两个指针，分别指着左右两边的第一个数，再准备一个空数组，左右比较，小的那个放空数组里，指针++；如果一个指针到头了，另一个整体拷贝进数组。
   2. 时间复杂度O(N*logN),空间复杂度O(N)
   3. mid = L +(R-L) >> 1(安全，不会产生溢出)
2. 归并算法的应用：
   
   1. 小和问题：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和，求一个数组的小和。
      
      1. 在找两个待merge的数组中，右边有多少个比前面指向的大，就产生多少个小和。
   2. 逆序对问题：如果左边的数比右边的数大，则两个数构成一个逆序对。请打印所有的逆序对。
      
      1. 在两个待merge的数组中，右边有多少个数比左边的小.
3. 归并算法应用，题目里如果出现了左，右根据大小做一些什么事情的时候，这个时候就很有可能利用的是归并的思想。

快排

1. partition问题：按照给定的num，小于等于放在数组左边，大于等于放在数组右边(额外空间复杂度O(1)，时间复杂度O(N)):
   
   1. 小于等于区域的指针x，从-1位置一直往下扩。cur从前向后遍历，
   2. 当前数如果大于num,跳过；
   3. 如果小于等于num,把这个数和x+1位置数交换，x++。
2. 荷兰国旗问题：小于放一边，中间放一边，大于放右边。（O(1),O(N)）:
   
   1. 准备两个表示区域的指针，小于区域less(-1)和大于区域more(N)。cur从前向后遍历，
   2. 如果当前数等于num，跳过，cur++；
   3. 如果小于num,当前数和less+1位置的数交换，less++，cur++；
   4. 如果大于num，当前数和more-1位置的数交换，more–,cur停在原地，考察换过来的值和num的大小。
   5. 停止条件为cur和more撞上。
3. 经典快排
   
   1. 数组最后一个为x，小于等于x的放左边，大于的放右边。左右再分别这么做。
   2. 一次划分，只搞定一个数
4. 改进的快排
   
   1. 用最后一个数做划分，小于的放左边，等于的放中间，大于的放右边。左右再划分，中间不用管。参考荷兰国旗问题。
   2. 一次划分，搞定了等于这一个区域的数。
5. 随机快排
   
   1. 经典快排的问题：用最后一个数去划分，很有可能造成左右两边的数据规模差距大，使算法变成O(N^2)
   2. 随机选择一个数做划分，用平均期望去估计复杂度。(O(NlogN)，额外空间复杂度O(logN))

堆排序

1. 堆：完全二叉树
2. 子节点和父节点的关系：假设父结点在数组中的位置为i,左孩子在数组中的位置为：2*i+1；右孩子为2*i+2(不越界条件下，越界相当于不存在);假设知道孩子结点的位置为i(无论左右),则父节点的位置为：(i-1)/2
3. 大根堆：在这棵完全二叉树中，任何子树的最大值均为其根节点。
4. 给定一个数组，构建大根堆(HeapInsert):(经历一个新来的数插入到已经有的大根堆的过程)
   
   1. 认为从0位置到i位置都是一个完全二叉树，i=0~N-1.在每一个完全二叉树中构建大根堆，也就是来一个数，跟他的父节点比，大就交换。然后大根堆的范围不断往下扩。
   2. 时间复杂度：O(N)
5. heapify（数组中（大根堆）中有个数变小了，如何调整(下沉)使再次成为大根堆）
   
   1. 找到它的左右两个孩子，其中最大的交换上去。也就是说变小之后的数下沉的过程。
   2. 应用：随时找到一个流中吐出数的中位数。
      
      1. 准备两个数组，一个构建大根堆，一个构建小根堆
      2. 流吐出来的第一个数放到大根堆里
      3. 新来的数如果比大根堆的堆顶大，放小根堆去，否则放大根堆，每放进去一次，都得进行一次heapInsert的操作
      4. 比较大根堆和小根堆的heapSize,如果大根堆比小根堆size大超过一，则把大根堆的堆顶弹出，放到小根堆；否则，小根堆的堆顶弹出，放大根堆。
      5. 这里有一个弹出堆顶的操作，实现：将堆顶和最后一个数交换，heapSize减1，然后剩下的堆来一次heapify操作。
      6. 重复上述过程，始终保持两个堆的size差不超过1
6. 堆排序
   
   1. 来了一个数组，先进行heapInsert操作，构建大根堆（这一步并不能保证数组一定有序，中间可能有乱的，但是堆顶一定是数组中的最大数）
   2. 把堆顶和数组最后一个数交换，heapSize–
   3. Heapify（每次搞定一个数，并且给放到数组末尾）
   4. 重复上述操作

排序算法的稳定性

工程中的综合排序算法

1. 先判断数据是五种基础类型还是用户定义的类型
   
   1. 基础类型：快排
   2. 自己定义的：归并排序
2. 数组长度很短（<60）：插排：常数项极低

有关排序问题的补充

1. 归并排序的额外空间复杂度可以达到O(1),但是非常难，“内部缓存法”
2. 快排可以做到稳定性问题，但是非常难。“01 stable sort”