基于比较类排序
基于比较的排序下界
交换排序
常见
- 冒泡
- 快排（根据冒泡改进）。
罕见
- 鸡尾酒排序
- 奇偶排序
- 梳排序
- 侏儒排序
- 臭皮匠排序
- Bogo排序
插入排序
常见
- 直接插入排序
- 希尔排序
罕见
- 伸展排序
- 二叉查找树排序
- 图书馆排序
- 耐心排序
选择排序
常见
- 直接选择排序
- 堆排序：https://liuzihua.top//archives/heapSort
罕见
- 平滑排序
- 笛卡尔树排序
- 锦标赛排序
- 圈排序
归并排序
常见
- 归并排序
罕见
- 梯级归并排序
- 振荡归并排序
- 多相归并排序
- 串列排序
非比较类排序
分布排序
常见
- 基数排序：https://liuzihua.top//archives/radixsort
- 计数排序
- 桶排序
罕见
- 美国旗帜排序
- 珠排序
- 爆炸排序
- 鸽巢排序
- 相邻图排序
- 闪电排序
- 插值排序
混合排序
罕见
- 块排序
- Tim排序
- 内省排序
- Spread排序
- J排序
并发类排序
罕见
- 双调排序器
- Batcher归并网络
- 两两排序网络
其他排序
罕见
- 拓扑排序
- 煎饼排序
- 意粉排序
算法复杂度
应用场景
排序算法的选择要考虑：数组大小、无序性、稳定应、空间。
- 数组大+要求稳定性+空间允许：归并
- 数组大：堆排序、快排、归并，因为他们是nlogn复杂度的方法。
- 中等大小数组：可以考虑希尔排序。
- 数组小（小于15）：冒泡、希尔排序、选择
- 无序性高：快排，也可以用希尔排序。
- 无序性低：插入、冒泡，他俩可降为O(n)。
