排序算法总结
基本概念
1. 时间复杂度
- 定义：一个算法流程中，常数操作数量的指标，这个指标叫做O，big O。具体为，如果常数操作数量的表达式中，只要高阶项，不要低阶项，也不要高阶项系数之后，剩下的部分记为f(N)，那么该算法的时间复杂度为O(f(N))
- 常数操作与数据量没有关系，时间复杂度和数据量有关，只要高阶项，且不要系数。
2. 空间复杂度
- 定义：给的数组不占额外空间，额外空间是为了完成排序还需要多少辅助的空间。
- 有限的几个变量是O(1)，长度为N的数组为O(N)。
3. 稳定性
- 定义：一个数组在排完序后，相等的值的相对次序不发生变化。
- 稳定性的作用：对引用类型的数据进行排序
4. 测试用例
随机生成数组，用自带的sort函数进行结果验证。引用类型数据还要写比对函数。
5. 递归和迭代
- 所有递归都可以改为迭代。递归是系统自己压栈，迭代就是自己压栈。
- 递归是自己调用自己，迭代是用while循环。
- 生产环境里不要用递归。
基于比较的的排序
时间复杂度不可能低于O(N*logN)
一、冒泡排序
- 时间复杂度：O(N^2)
- 额外空间复杂度：O(1)
- 是否可实现稳定性：是
1. 原理
从第一个数开始，比较相邻的两个数，大的数往下沉，每次排好未排序序列中的最大数。
2. 交换两个数据的方法
(1)用temp变量保存。
var temp=a;
a=b;
b=temp;
(2)异或运算(XOR)。
异或满足交换律和结合律，就是无进位相加，1+0=1,0+1=1,1+1=0。
缺点：float类型且引用地址相同不能用该方法。
a=a^b;
b=a^b;
a=a^b;
3. 时间复杂度
N+N-1+....+1=N(N+1)/2；只要高阶项，不要低阶项，也不要高阶项系数，因此为O(N²)。
4. 空间复杂度
冒泡排序只需要几个有限的变量空间，所以是O(1)。
5. 稳定性
相等的不交换，大于时交换，就可以保证稳定性。
二、插入排序
- 时间复杂度O(N^2)
- 额外空间复杂度O(1)
- 是否可实现稳定性：是
1. 原理（类似扑克牌）
插入排序就是，在有序区中，从后往前，遇到大于自身的数就进行交互换，看什么时候停下来。直到最后一个数加入有序区。
2.空间复杂度
最差情况下1+...+N-1=(N-1)N/2，因此为O(N²)。
3. 空间复杂度
只需要几个有限的变量空间，所以是O(1)。
4. 稳定性
相等的不交换，只有大于时交换，就可以保证稳定性。
三、选择排序
- 时间复杂度O(N^2)
- 额外空间复杂度O(1)
- 是否可实现稳定性：否
1. 原理
每次从无序区中选择最小的数加入到有序区的末尾。与相应位置的数据进行交换
2.空间复杂度
每次遍历找最小值：N+N-1+....+1=N(N+1)/2，因此为O(N²)。
3. 空间复杂度
只需要几个有限的变量空间，所以是O(1)。
四、快速排序
- 时间复杂度O(N*logN)
- 额外空间复杂度必须为O(logN)
- 是否可实现稳定性：额外空间复杂度为O(logN)的情况下不可以，增加额外空间可以，但快排要求的就是空间复杂度为O(logN)。
logN默认以2为底，代表长度为N的数组可以二分多少次。
1、求M([3,1,5,4,2])中不在N([9,2,7])中的数的集合，即求M-N的差集
(1)暴力搜索
将M中每个数依次与N中的数进行遍历对比，不在N中就打印，在N中就直接跳过。
时间复杂度O(MN)。
(2)先排序再二分
- N先排序，M中每个数通过二分搜索的方式确定有没有。
- 排序时间复杂度为O(A)，二分搜索时间复杂度为O(MlogN)。该方法的总时间复杂度为O(A)+O(MlogN)，化简后为其中的大者。
- L+(R-L)/2 = L+(R-L)>>1，位运算比除法快
2、随机快排原理
- 经典快排：将小于等于划分为一个区域。
- 改进快排：将小于和等于分为两个区域。随机找一个数作为基准，小于这个数的放左边，等于的放中间，大于的放右边，然后再递归将左右边进行排序
3、代码实现
(1)如果为null或者length<2，直接返回
(2)随机选择一个数作为基准数，交换至数组末尾
(3)partition返回等于基准数的左右边界下标，再递归的对小于区和大于区进行快排。
4、时间复杂度
(1)选一个随机的划分数，为O(1)。
(2)partition过程，将数组划分为三个区间，就是遍历一次数组的过程为O(N)。
(3)左侧和右侧分别进行了递归。
- 最差情况下，每次O(N)只能搞定一个数（1,2,3,4,5,6选择第一个数为划分数），最终复杂度为O(N²)。因此通过随机选择划分值可以在概率上尽量避免出现最差的情况。
- 最好情况下，左右差不多都是N/2，2T(N/2)，用master公式计算，a=b=2，d=1，因此T(N)=N*logN。master公式只能用于递归规模一样的情况。
- 概率累加得到的期望值也为N*logN。
5、空间复杂度
因为左右需要递归排序，过程中需要不断记录划分值的位置，因此空间复杂度为断点树的高度，即log(2)(N)
五、归并排序
- 时间复杂度O(N*logN)
- 额外空间复杂度O(N)
- 实现可以做到稳定性
1、原理
- 递归法：将数组二分直至不能划分，即每个组都只有一个数值，然后不断合并排序。
- 迭代法：room=1、2、4、8....不足就保持不变，不断排序合并
2、小和问题
- 问题：将每个数的左边所有比它小的数进行累加，得到的和为小和。
- 思路：对每个数而言，只需要知道我的右边有多少个数比我大，我就累加几次。通过归并排序，在merge的的过程中，会依次遇到所有右边比我 大的数。
3、求逆序对
- 问题：存在多少对数对，数对中前面的数比后面的数大。
- 思路：和小和问题同理，即对每个数而言，只需要知道我的右边有多少个数比我小，在我这个位置就产生了多少对逆序对。
六、堆排序
- 时间复杂度O(N*logN)
- 额外空间复杂度O(1)
- 实现不能做到稳定性
关键步骤：heapInsert, heapify，堆的扩大和缩小操作
1、堆的概念
- 完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
- 平衡二叉树(AVL树)：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定。
- 堆(算法上的堆，不是系统中的堆)就是一个完全二叉树，可以把一个数组在逻辑上对应成一颗完全二叉树，左孩子2i+1，右孩子2i+2，父(i-1)/2。
- 大根堆：一定是一个完全二叉树结构，任何一个根节点都是其所在数树(子树)中的最大值。
2、原理
（1）将数组变换为大根堆。每个数和父节点的值进行比较，如果大于父节点，就交换。时间复杂度=log1+log2+log3+...+logN=O(N)。
（2）此时根节点的值最大，然后交换根节点和最后一个节点，保持最后一个节点不动，size--，超过size就代表越界。然后再构建大根堆，以此往复，每次找打最大值，直至所有数据排完序。
最重要的heapinsert（初始化构建大根堆），heapify（下沉函数），size。优先级队列的题目就是堆，建立堆的过程和任何一个堆沉下去的过程重要。
4、时间复杂度
（1）建立大根堆的过程为O(N)。
（2）heapify的过程就是树的高度，为O(logN)。
（3）N个数的时间复杂度就是O(NlogN)，但常数项很大。
5、堆排和快排对比
- 空间复杂度：堆排的空间复杂度可以做到O(1)是因为它的父子节点是通过公式的方式找到的，而快排需要记录断点的位置。
- 时间复杂度：堆排的常数项很大，不存在最好和最坏情况；快排的常数项小。
七、希尔排序
插入排序，就是步长为1的希尔排序。
八、系统中的排序原理
- 数据量<60，插入排序，复杂度高，常数项少；
- 数据量大的情况下，快速排序。
不基于比较的的排序
不基于比较的排序是有瓶颈的，对数据的位数和范围有限制。
桶排序
桶排序只是一个概念，基数排序和计数排序是桶排序的具体实现。
一、计数排序
先准备好相应数量的桶，然后遍历数据，将其放入对应的桶中，最后将桶中的数依次倒出来。
二、基数排序
- 取位数最多的记录，其他不足该位数的补0。
- 按照个位数字依次放入桶中。
- 从0号桶开始，依次倒出来。先入桶的先倒（队列结构）。
- 按照十位数进桶，再倒出来，如此反复，直到最高位，结束。
