- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
快速排序是一种高效快速的算法，是Hoare于1962年提出的一种二叉树结构的交换排序方法，
其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
根据其思想 ，便有递归版本 和 非递归版本。
递归版本中有 Hoare版本， Hole版本，前后指针版本。
非递归版本使用 栈 来实现。
2.1.1 Hoare版本
2.1.2 hole版本
2.1.3 前后指针法
2.1.4 注意
取中位数
局部优化
根据二叉树的相关知识，最后一层包含50%数据，倒数第二层包含25%数据，倒数第三层包含12.5%数据。
第n层 递归 1 次 第 n-1 层 递归 2 次 第 n - 2 层 递归 4 次 … 第 1 层 递归 2^n 次
所以在进行绝大部分的排序后，如果继续进行递归会存在问题，此时递归次数非常多。所以我们进行局部优化，在数据小于10个（取决于具体数据）时改换为插入排序等稳定算法即可。
2.1.5 非递归版本
非递归算法通常要使用一些循环来达到全部遍历的目的。也使得 非递归版本 比 递归版本 更需要对“递归”的深入理解，这里快速排序的非递归版本使用栈来模拟递归过程。
非递归原理
栈里面依次存放了应该排序的部分，每次取出两个，来进行排序（注意取出顺序与存入顺序相反，若先入左 则先取的为右），排序完毕，存入左右部分的开始位置与结束位置，直到有序。
排序步骤
- 存入开始位置begin 结束位置end ，key值取左值。
- 依次出栈 记录右位置 right ，左位置 left（读取顺序很重要），排序 该部分
- 以key值分割左右两部分，压栈存入左部分的开始与结束位置，压栈存入右部分的开始与结束位置。(若left >= key不读取左部分 若 right<=key 不读取右部分)
- 依次出栈 记录右位置 right ，左位置 left（读取顺序很重要），排序 该部分
- 重复2 - 3步骤,直到栈为空。
- 完成排序
代码实现
栈相关知识
快速排序的特性总结：
-
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
-
空间复杂度：O(logN)