【数据结构】十大经典排序算法总结与分析

前言

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

前面通过11篇内容的学习，我们已经深刻的了解了十大经典排序算法，本文将对这十大经典算法进行总结，比较与分析。

1. 十大经典排序算法分类

十种常见排序算法可以分为两大类：

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破$O(nlogn)$，因此称为非线性时间比较类排序。

线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

2. 相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
• 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
• 内排序：所有排序操作都在内存中完成；
• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
• **时间复杂度：**时间复杂度就是时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。
• 空间复杂度：空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度

3. 十大经典算法总结

名词解释：

• n: 数据规模
• k: “桶”的个数
• In-place: 占用常数内存，不占用额外内存
• Out-place: 占用额外内存

4. 补充内容

4.1 比较排序和非比较排序的区别

• 常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
  在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为$O(n^2)$。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为$logn$，所以时间复杂度平均$O(nlogn)$。

  比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

• 计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。
  非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度$O(n)$。

  非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

4.2 稳定的算法就真的稳定了吗？

算法思想的本身是独立于编程语言的，所以你写代码去实现算法的时候很多细节可以做不同的处理。采用不稳定算法不管你具体实现时怎么写代码,最终相同元素位置总是不确定的(可能没变也可能变了)。

而稳定排序算法是你在具体实现时如果细节方面处理的好就会是稳定的,但有些细节没处理得到的结果仍然是不稳定的。

4.3 稳定的意义

如果我们只是面对简单的数字排序，那么稳定性确实也没有多大意义。比如1 2 3 3 4的序列中如果第一个3和第二个3在sort方法反复执行之后位置也反复变化，但是对于调用sort方法所想要获得排序结果的上游应用而言，那么结果还是1 2 3 3 4，至于3的次序，无关紧要。

如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（所谓的交换操作的开销已经算在算法的开销内了，如果嫌弃这种开销，不如换算法好了？）

如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。

那么排序算法的「稳定性」在什么情况下才会变得有意义呢？

举个例子，一个班的学生已经按照学号大小排好序了，我现在要求按照年龄从小到大再排个序，如果年龄相同的，必须按照学号从小到大的顺序排列。那么问题来了，你选择的年龄排序方法如果是不稳定的，是不是排序完了后年龄相同的一组学生学号就乱了，你就得把这组年龄相同的学生再按照学号排一遍。如果是稳定的排序算法，我就只需要按照年龄排一遍就好了。

（从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法。）

排序算法的「稳定性」有何意义？这个还是要分应用场景来看，很多使用情况下，并没有什么实质的意义，而在有些情况下却有很重要的意义。

有很多算法你现在看着没啥，但是当放在大数据云计算的条件下它的稳定性非常重要。举个例子来说，对淘宝网的商品进行排序，按照销量，价格等条件进行排序，它的数据服务器中的数据非常多，因此，当时用一个稳定性效果不好的排序算法，如堆排序、shell排序，当遇到最坏情形，会使得排序的效果非常差，严重影响服务器的性能，影响到用户的体验。

4.4 时间复杂度的补充

一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。设每种情况的出现的概率为$pi$,平均时间复杂度则为$sum(pi\ast f(n))$。

4.5 空间复杂度补充

利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。程序执行时所需存储空间包括以下两部分：
（1）固定部分：这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
（2）可变空间：这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

空间复杂度所考虑的是可变空间这一部分。

结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。

也可以点点关注，避免以后找不到我哦！

Crossoads主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的动力！

带你初步了解排序算法：https://blog.csdn.net/2301_80191662/article/details/142211265
直接插入排序：https://blog.csdn.net/2301_80191662/article/details/142300973
希尔排序：https://blog.csdn.net/2301_80191662/article/details/142302553
直接选择排序：https://blog.csdn.net/2301_80191662/article/details/142312028
堆排序：https://blog.csdn.net/2301_80191662/article/details/142312338
冒泡排序：https://blog.csdn.net/2301_80191662/article/details/142324131
快速排序：https://blog.csdn.net/2301_80191662/article/details/142324307
归并排序：https://blog.csdn.net/2301_80191662/article/details/142350640
计数排序：https://blog.csdn.net/2301_80191662/article/details/142350741
十大经典排序算法总结与分析：https://blog.csdn.net/2301_80191662/article/details/142211564

参考内容：如果我问你：排序算法的「稳定性」有何意义？你怎么回答？ (qq.com)

十大经典排序算法的复杂度分析_排序算法时间复杂度-CSDN博客