前言

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

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

前面通过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/142211564

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

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