排序算法对比总结
前提提要：建议请先阅读以下三篇文章，了解本篇所对比的五种算法的基本思想及代码。
https://blog.ZEEKLOG.net/2301_79932175/article/details/157397676?spm=1001.2014.3001.5501
https://blog.ZEEKLOG.net/2301_79932175/article/details/157652329?spm=1001.2014.3001.5501
https://blog.ZEEKLOG.net/2301_79932175/article/details/157691325?spm=1001.2014.3001.5501
一、算法对比总结表
排序 算法 | 平均 时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 是否 稳定 | 核心思想 |
|---|---|---|---|---|---|---|
冒泡 排序 | O( | O( | O( | O(1) | 是 | 相邻元素两两比较交换，将最大/小值“冒泡”到一端。 |
选择 排序 | O( | O( | O( | O(1) | 否 | 从未排序部分选出最小（大）元素，放到已排序部分的末尾。 |
插入 排序 | O( | O( | O( | O(1) | 是 | 将元素插入到已排序序列的合适位置，类似整理扑克牌。 |
快速 排序 | O( | O( | O( | O( | 否 | 分治。选取基准，将数组分为小于和大于基准的两部分，递归排序。 |
归并 排序 | O( | O( | O( | O( | 是 | 分治。将数组递归地对半拆分，再将有序子数组合并。 |
二、详细解析
1、冒泡排序
工作原理
重复遍历列表，比较相邻元素，如果顺序错误就交换。每次遍历会将当前未排序部分的最大元素“冒泡”到最后。
优点
- 实现简单，代码直观。
- 是稳定排序。
对于已经基本有序的序列，优化后的版本（设置交换标志flag）可以达到接近O(
)的时间复杂度。
缺点
效率低，在数据量大时几乎不可用。
适用场景
小规模数据。
2、选择排序
工作原理
将数组分为“已排序”和“未排序”两部分，每次从“未排序”部分中找到最小（或最大）元素，将其与“未排序”部分的第一个元素交换，从而将其纳入“已排序”部分。
优点
- 实现简单。
- 交换次数少，对于交换成本高的数据有一定优势。
缺点
- 不稳定。
时间复杂度恒为 O(
)，与数据初始状态无关，非常低效。
适用场景
数据量小，且对稳定性无要求，同时希望减少交换次数的情况。
3、 插入排序
工作原理
将数组分为“已排序”和“未排序”两部分，每次取出“未排序”部分的第一个元素，在“已排序”部分中从后向前扫描，找到相应位置并插入。
优点
- 实现简单。
- 稳定排序。
- 对于小规模或基本有序的数据集，效率非常高。
缺点
平均和最坏情况仍是 O(
)，不适合大规模乱序数据。
适用场景
- 小数组的排序。
- 部分有序数组的排序。
4、快速排序
工作原理
- 分区：从数组中选取一个“基准”元素。
- 排序：将数组重新排列，所有小于基准的元素放在其前面，所有大于基准的放在后面（等于的放哪边都可以）。此时基准处于其最终位置。
- 递归：递归地对基准前、后的子数组进行快速排序。
优点
平均性能好，是大多数编程语言标准库的默认排序实现基础。
缺点
- 不稳定
最坏情况（如数组已有序或逆序，且基准选择不当）下时间复杂度为O(
)。通过随机化选择基准或“三数取中法”可以有效避免。
适用场景
处理随机数据大规模排序。
5、归并排序
工作原理
- 分割：递归地将数组对半分成两个子数组，直到子数组只有一个元素（自然有序）。
- 合并：递归地将两个有序的子数组合并成一个大的有序数组。合并过程是算法的关键。
优点
- 稳定排序。
时间复杂度稳定
。
缺点
对于小规模数据，递归和合并的开销可能使其比优化过的插入排序慢。
适用场景
大规模外部排序。
