前面讲了大多数常见的排序算法，这里对这些算法总结一下
算法属性列表
| 排序算法 | 最优时间复杂度 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 是否稳定 | 是否为原地排序 |
|---|---|---|---|---|---|---|
| 选择排序 | Ω(n2) | Θ(n2) | O(n2) | O(1) | N | Y |
| 插入排序 | Ω(n) | Θ(n2) | O(n2) | O(1) | Y | Y |
| 冒泡排序 | Ω(n) | Θ(n2) | O(n2) | O(1) | Y | Y |
| 希尔排序 | Ω(n) | Θ(n1.3) | O(n2) | O(1) | N | Y |
| 归并排序 | Ω(nlogn) | Θ(nlogn) | O(nlogn) | O(n) | Y | N |
| 快速排序 | Ω(nlogn) | Θ(nlogn) | O(n2) | O(logn) | N | Y |
| 堆排序 | Ω(nlogn) | Θ(nlogn) | O(nlogn) | O(1) | N | Y |
| 计数排序 | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) | Y | N |
| 基数排序 | Ω(n*q) | Θ(n*q) | O(n*q) | O(n+k) | Y | N |
| 桶排序 | Ω(n+k) | Θ(n+k) | O(n+k) | O(n+k) | Y | N |
快速排序算法总结
快排是目前最快的通用排序算法
原因：快排的内循环指令少，而且大多采用顺序取值可以充分利用缓存
利用稳定性排序算法可以在保持原来的属性A的有序性下，实现属性B的有序，这时候B的顺序优先
排序算法解决的问题归约
- 找出重复元素
- 排名
- 优先队列
- 中位数与顺序统计
排序算法应用
- 商业计算
- 信息搜索
- 运筹学
- 事件驱动模拟
- 数值计算
- 组合搜索
END
2019-03-12 完成
2019-03-05 立项