关于排序算法，面试环节都会怎么问？

深碍√TFBOYSˉ_ 2023-02-25 02:08 93阅读 0赞

点击上方“**五分钟学算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

来源：景禹

前段时间，好多小禹禹征询是否可以更新排序算法相关的内容，所以就有了这个 「排序算法」专题，也很感谢这些提需求的小禹禹，恭喜你是第一次看到这个专题，也希望你从中有所收获。今天主要针对一些排序算法最基本的问题给出回答，如果有所困惑，欢迎评论区留言分享，后面在更新的时候，景禹就都会考虑进来。

### 什么是就地排序（in-place sorting）？ ###

一个就地排序算法使用恒定的的额外空间来产生输出（仅修改给定的数组）。它仅通过修改线性表中元素的顺序来对线性表进行排序。例如，插入排序（Insertion Sort）和选择排序（Selection Sort）是就地排序算法，因为它们不使用任何额外的空间来对线性表进行排序。而归并排序（Merge Sort）和计数排序（Counting Sort）的经典实现就不是就地排序算法。

### 什么是内部排序和外部排序？ ###

当所有待排序记录不能被一次载入内存进行处理时，这样的排序就被称为外部排序。外部排序通常应用在待排序记录的数量非常大的时候。归并排序以及它的变体都是典型的外部排序算法。外部排序通常与硬盘、CD等外部存储器（辅存）关联在一起。

当所有待排序记录可以一次载入内存时，则称为内部排序。

### 什么是稳定排序？ ###

当我们对可能存在重复键的键值对（例如，人名作为键，其详细信息作为值）按照键对这些对象进行排序时，稳定性就显得至关重要。

#### 如何判定一个排序算法的是稳定的呢？ ####

如果两个具有相等关键字的对象在排序前后的相对位置没有发生变化，则认为排序算法是稳定的。可以形式化地描述为：

设表示一个待排序的数组，表示数组的一个严格的弱排序（即有重复元素）。一个排序算法稳定，当且仅当，且隐含，其中表示排序后的序列（排序算法将移动到了的位置，将移动到了的位置，但是和的相对位置保持不变）。

形式化感觉瞬间高大上，但是景禹一贯风格，通俗易懂，所以看一下下面的例子。

![format_png 2][]

图中展示的就是稳定排序的例子，简单来讲，排序前，青色球 `10` 在红色球 `10` 的前面，那么排序后两者的相对位置并没有改变，青色球 `10` 还是在红色球的前面；排序前红色球 `20` 在青色球 `20` 的前面，则排序后两者的两者的位置没有发生变化，依旧是红色在青色的前面。

简而言之，**排序前后序列中键值相等的元素的相对位置没有发生变化的就是稳定排序**。

### 难道我们仅关心像整数数组这样的简单数组？ ###

当键值相等的元素不可区分时，例如整数，或更一般地说，用于排序的键值即为数据本身，稳定性无足轻重。同样，当所有键值都不相同，那么也不用去关注排序算法的稳定性问题。但真实情况是复杂的，往往是对一个复杂类型的数组排序，而排序的键值仅是这个元素的一个属性。对于一个简单类型（整型），数字值就是其全部意义，即使交换了也看不出什么不同。但是对于复杂的类型，交换的话可能就会使原本不应该交换的元素交换了。比如，一个“学生”数组，按照年龄属性排序，“学生”这个对象不仅含有“年龄”，还有其他很多属性，稳定排序会保证比较时，如果两个年龄相同的学生的相对位置不变。

一起看一个简单的例子，来理解一下这上面一段话。

考虑以下球星姓名及其各自的等级（段位）数据集。

![format_png 3][]

如果仅根据球星的姓名对数据进行排序，则结果数据集也不太可能根据他们各自的等级进行分组。

![format_png 4][]

因此，我们可能还必须再次按照等级进行排序才能获得一个满意的球星名单。此时如果排序算法不稳定，我们可能会得到如下结果：

![format_png 5][]

此时根据球星的等级进行了排序，但却忽略了球星的姓名次序。在原始的数据集当中，Bill（比尔）是在 Embiid（恩比德）的前面的，但是当排序算法不稳定时，这种相对次序被丢失了。

而使用稳定的排序算法对原始数据集按照等级进行排序，就不会丢失这些相对次序信息，稳定排序结果：

![format_png 6][]

上图中稳定排序保证原始数据中元组之间的相对次序信息保留了下来，这也正是我们所需要看到的。

哈哈，这里顺带说一下，杜兰特、詹姆斯、库里、比尔、恩比德我都挺喜欢，个人认为他们等级都是 No. 1，这里为了说明问题才捣鼓出的 A 和 B。希望没有激怒忠实球友~~

### 哪些排序算法是稳定的呢？ ###

冒泡排序（Bubble Sort）、插入排序（Insertion Sort）、归并排序（Merge Sort）和计数排序（Counting Sort）等本身就具有稳定排序的特质。

基于比较的排序算法，例如归并排序和插入排序，他们是如何保证稳定性的呢？

就升序排列而言，元素位于之前当且仅当，表示数组的索引且。当时，如果，也就是位于之前，原始数据中的相对次序才能被保留下来。

非基于比较的排序算法，例如计数排序，通过确保以相反的顺序填充已排序的数组来保持稳定性，以使键值相等的元素的的相对位置不变。

### 哪些排序算法是不稳定的呢？ ###

快速排序（Quick Sort）和 堆排序（Heap Sort）等就是不稳定的排序算法，但是这些排序算法可以通过将元素的相对次序考虑进来而变得稳定，方法就是空间换时间，开辟一些额外的空间（大概) 以实现稳定性。

### 是否可以使任何排序算法都变得稳定呢？ ###

答案是肯定的。任何排序算法都可以通过指定的方式变得稳定，可以通过修改键值的比较操作将本质上不稳定的任何基于比较的排序算法修改为稳定，保证键值相等的两个元素在排序前后的相对位置不变。

排序算法初探就到这里，没有学过相关排序算法，难免会对哪些排序算法稳定，哪些排序算法不稳定理解不是很到位，但是至少你知道了什么是稳定排序，知道了什么是，喜欢景禹的文章（或者景禹）就点个文末的在看，周六愉快呀~~

--------------------

### **推荐阅读** ###

• [吴师兄实名吐槽 LeetCode 上的一道题目。。。][LeetCode]• [面试字节跳动时，我竟然遇到了原题……][Link 1]• [计算机网络基础知识总结][Link 2]• [张一鸣：我的大学四年收获及工作感悟][Link 3]• [一道简简单单的字节跳动算法面试题][Link 4]• [又一 VSCode 神器诞生！][VSCode]• [如果张东升是个程序员][Link 5]

--------------------

欢迎关注我的公众号“**五分钟学算法**”，如果喜欢，麻烦点一下“**在看**”~

![format_png 7][]

[format_png]: /images/20230209/c9c58230d9c4406a952a74872c532d1e.png
[format_png 1]: /images/20230209/484ca732ad2d48fe9f515a7491ec5354.png
[format_png 2]: /images/20230209/d79e4cf6550b497d9d59b6206ced2b99.png
[format_png 3]: /images/20230209/bdfb9236913542a7aceb75ede238a5e3.png
[format_png 4]: /images/20230209/4f8aad924c1f4091b9e080e34efaa8ba.png
[format_png 5]: /images/20230209/8edfbd6f345442b99043145737df0e75.png
[format_png 6]: /images/20230209/9ee28b3486704f358cc8d4fc829dac37.png
[LeetCode]: https://blog.csdn.net/kexuanxiu1163/article/details/106846242
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/106774199
[Link 2]: https://blog.csdn.net/kexuanxiu1163/article/details/107031577
[Link 3]: https://blog.csdn.net/kexuanxiu1163/article/details/107118022
[Link 4]: https://blog.csdn.net/kexuanxiu1163/article/details/106740545
[VSCode]: https://blog.csdn.net/kexuanxiu1163/article/details/107194086
[Link 5]: https://blog.csdn.net/kexuanxiu1163/article/details/107132914
[format_png 7]: /images/20230209/42c96682e0ca4478a987ff48bcbc9b37.png