快速排序
选出一个值作为基准值，把比它小的值移到左边，比它大的移到右边。然后对两边做同样的事。
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- 否
- 是
最佳：输入对这个算法最容易时，时间随列表大小 n 增长的方式。
平均：时间随 n 的一般增长。n² 表示值的个数翻倍时耗时约为四倍；n log n 增长得慢得多。
最差：最难的输入下的增长。适合速度绝不能下降的场合。
内存：除列表外还需要多少额外内存。1 表示几个变量，n 表示一份列表副本。
稳定：两个相等的值保持原来的顺序。按记录的某个字段排序时很重要。
无需额外内存：直接在列表内部排序，不用第二个列表。
- 比较中
- 移动中
- 基准值
- 已就位
试试看： 选一个逆序的列表。基准值总是剩下的最小值或最大值，所以每次划分都有一边是空的，代价逐渐接近 n²。
工作原理
这里的基准值是区间里的最后一个值。从左到右看，每个不大于基准值的值都被交换到左边。然后把基准值放到两组之间，它从此不再移动。两组再各自用同样的方法排序。
适用场合
实际使用中最快的排序方法之一，而且几乎不需要额外内存。但如果总是选到不好的基准值，它就会变慢，比如列表本来就排好的时候。实际的实现会更谨慎地选基准值。