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

9 阅读 0 评论 0 点赞

虽然在竞赛和编程语言中用到的排序算法主要是时间复杂度为 $\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)}$	$\log n)$

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

点赞(0) 打赏

暂无评论