常见的排序算法及分类对比

虽然在竞赛和编程语言中用到的排序算法主要是时间复杂度为 $O(n\log n)$ 的高效算法，但作为算法学习，我们要从简单到复杂，认识常见的排序算法，并理解其算法思想。本文列出几乎所有的排序算法并进行分类对比。

排序算法总表

以下是一个对比表格，涵盖几乎所有常用的排序算法：

名称	算法思想	平均时间 复杂度	最优时间 复杂度	最坏时间 复杂度	空间 复杂度	稳定排序	内排序	原地排序	比较排序	备注
冒泡排序	相邻交换，逐步冒泡	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳	内	原	是	可优化（如鸡尾酒排序），不适合大数据。
选择排序	每次选择最小/最大元素	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不	内	原	是	简单实现，适合小规模数据。
插入排序	构建局部有序序列 （ 像抓牌）	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳	内	原	是	基于简单插入的排序，针对字符串可以折半插入。
希尔排序 Shell Sort	改进插入，分组和逐步缩小间隔	$O(n^{1.5)}$	$O(n\log n)$	O