常见的排序算法及分类对比
虽然在竞赛和编程语言中用到的排序算法主要是时间复杂度为 O ( n log n ) O(n \log n) O(nlogn) 的高效算法，但作为算法学习，我们要从简单到复杂，认识常见的排序算法，并理解其算法思想。本文列出几乎所有的排序算法并进行分类对比。
排序算法总表
以下是一个对比表格，涵盖几乎所有常用的排序算法：
| 名称 | 算法思想 | 平均时间 复杂度 |
最优时间 复杂度 |
最坏时间 复杂度 |
空间 复杂度 |
稳定排序 | 内排序 | 原地排序 | 比较排序 | 备注 |
|---|---|---|---|---|---|---|---|---|---|---|
| 冒泡排序 | 相邻交换，逐步冒泡 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 稳 | 内 | 原 | 是 | 可优化（如鸡尾酒排序），不适合大数据。 |
| 选择排序 | 每次选择最小/最大元素 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 不 | 内 | 原 | 是 | 简单实现，适合小规模数据。 |
| 插入排序 | 构建局部有序序列 （ 像抓牌） | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 稳 | 内 | 原 | 是 | 基于简单插入的排序，针对字符串可以折半插入。 |
| 希尔排序 Shell Sort |
改进插入，分组和逐步缩小间隔 | O ( n 1.5 ) O(n^{1.5)} O(n1.5) | O ( n log n ) O(n \log n) O(nlogn) | O |