十大经典排序算法复杂度、应用场景总结 | 插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序、桶排序、计数排序

前言

好久不见辽，uu们！这几天由于准备专业课的课堂pre，因此一直没能给 “c++实现十大经典排序算法” 系列结个尾。本次的十大排序算法包括：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序、桶排序、计数排序，有关以上排序算法的原理介绍及代码分享的文章都放在了本篇的末尾，感兴趣的佳人可以点击链接，“ 嗖 ” 的一下传送过去哈！

今天这篇文章，主要是对前段时间连更的排序算法的总结，包括每个算法的复杂度、使用场景等。所有分享均来自学校算法课的总结和网上资料搜集的总结，并且是自己思考过认为正确的内容（主要思考依据是已经ac过的代码），如果uu们在观看本系列文章的任何一篇中有所疑问，欢迎在评论区交流分享。

十大算法的复杂度总结

以下图片来自于 1.0 十大经典排序算法 | 菜鸟教程 (runoob.com)

稳定性是指在排序算法完成后，大小相等的值的顺序和它们最初的先后顺序一致，在需要保持原始顺序或者相同关键字元素的相对顺序不变的应用场景中，稳定排序算法能够提供更可靠的排序结果，确保后续处理和分析的正确性。例如在教务系统中，对我们的成绩进行排名——刚开始教务系统的名单中肯定是按学号排序的，当在此基础上按照成绩排序时，假如有多名学生成绩相同，使用稳定性的排序算法可以保持相同成绩学生的原始顺序，即序号小的在前。

排序算法可以分为内部排序和外部排序，这是根据排序过程中数据存放的位置不同而划分的两种排序方式。

内部排序（Internal Sorting）： 内部排序是指所有待排序的数据都能够一次性载入内存，并且排序过程中所有的操作都在内存中进行。内部排序适用于数据量较小，可以完全存放在内存中的情况。
外部排序（External Sorting）： 外部排序是指待排序的数据量太大，无法一次性载入内存，需要借助外部存储（如磁盘、SSD等）进行排序。外部排序通常分为两个阶段：首先在内存中对数据进行部分排序（通常称为初步排序或者分段排序），然后将部分排序后的数据写入外部存储，最后对外部存储中的数据进行归并排序等操作得到最终的排序结果。

对于以上十种排序算法：

内部排序算法：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序。
外部排序算法：基数排序、桶排序、计数排序。

内部排序算法通常适用于数据量较小的情况，因为它们的排序过程可以完全在内存中进行，而外部排序算法适用于数据量较大，无法一次性载入内存的情况，因为它们可以将数据分批加载并排序。

该部分理论到此结束，不过在目前刷题时，只要是排序，我们一般都直接使用STL中封装好的的sort()函数，sort()帮我们实现了快速排序算法，并且我们可以自己设定排序方式，使其实现升序、降序或者对结构体等的排序。总之，主打一个方便。

算法的应用场景

插入排序： 适用于小规模数据或者部分有序的数据。由于插入排序在处理小规模数据时性能较好，并且对部分有序的数据具有稳定性，因此常用于对已经接近有序的数据进行排序，或者作为其他排序算法的优化手段。
希尔排序： 适用于中等规模数据，特别是对于大规模数据的排序。希尔排序通过增量序列将数据分组并分别进行插入排序，能够在一定程度上提高插入排序的效率，因此适合处理大规模数据的排序问题。
选择排序： 适用于小规模数据，但在实际应用中效率较低。选择排序每次选择未排序部分中的最小元素放置到已排序部分的末尾，因此适合处理小规模数据的排序，但由于其时间复杂度较高，不适合处理大规模数据。
冒泡排序： 适用于小规模数据，但在实际应用中效率较低。冒泡排序通过比较相邻元素并交换，将较大（或较小）的元素逐步移动到末尾，因此适合处理小规模数据的排序，但时间复杂度较高，不适合处理大规模数据。
归并排序： 适用于任意规模的数据，特别是对于大规模数据的排序。归并排序采用分治法将数据分解为小问题并逐步解决，然后将解合并起来，因此适合处理大规模数据的排序问题，并且具有稳定性。
快速排序： 适用于任意规模的数据，特别是对于大规模数据的排序。快速排序采用分治法，通过选择一个基准元素将数据分为两部分，并递归地对每部分进行排序，因此能够快速地处理大规模数据的排序问题。
堆排序： 适用于任意规模的数据，特别是对于大规模数据的排序。堆排序通过构建一个堆结构来实现排序，具有较好的时间复杂度和空间复杂度，并且能够处理大规模数据的排序问题。
基数排序： 适用于数据范围较小但数据量较大的情况。基数排序将数据按照位数进行排序，从低位到高位依次排序，因此适合处理数据范围较小但数据量较大的排序问题。
桶排序： 适用于数据范围较小但数据量较大的情况。桶排序将数据分为若干个桶，并将数据分配到不同的桶中，然后对每个桶中的数据进行排序，最后合并桶中的数据，因此适合处理数据范围较小但数据量较大的排序问题。
计数排序： 适用于数据范围较小且数据量较大的情况。计数排序统计数据中每个元素出现的次数，并根据统计结果将数据排序，因此适合处理数据范围较小但数据量较大的排序问题，并且具有稳定性。本质上来说，基数排序、桶排序、计数排序都是使用了“桶”的思想，所以适用范围基本一致。