面试官：冒泡、插入、选择这三种常见的排序算法你了解？为什么插入排序更受欢迎？

深藏阁楼爱情的钟 2023-07-18 14:13 20阅读 0赞

> 排序算法应该是我们每个人刚开始学习时都会接触的，应该是大部分人学习的第一个算法。常见的排序算法非常多，比如猴子排序、睡眠排序、面条排序等。这里我们只学习下最常见、最经典的排序算法。

按照算法的时间复杂度，可以分为以下三类，我们对着分类去学习，更能加深记忆和对算法的掌握。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70][]

## 如何分析一个“排序算法”？ ##

### 排序算法的执行效率 ###

1.  最好情况、最坏情况、平均情况时间复杂度
2.  时间复杂度的系数、常数 、低阶
3.  比较次数和交换（或移动）次数

### 排序算法的内存消耗 ###

算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过，针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。

### 排序算法的稳定性 ###

仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，我们还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

我通过一个例子来解释一下。比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；**如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。**

## 冒泡排序（Bubble Sort） ##

> 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

我用一个例子，带你看下冒泡排序的整个过程。我们要对一组数据 4，5，6，3，2，1，从小到大进行排序。第一次冒泡操作的详细过程就是这样：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 1][]

可以看出，经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进行 6 次这样的冒泡操作就行了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 2][]

实际上，刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。我这里还有另外一个例子，这里面给 6 个元素排序，只需要 4 次冒泡操作就可以了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 3][]

冒泡排序算法的原理比较容易理解，具体的代码我贴到下面，你可以结合着代码来看我前面讲的原理。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 4][]

## 插入排序 ##

> 首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束.

如图所示，要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 5][]

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。

代码部分也不难，如下所示：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 6][]

**注意，这里是从尾到头遍历已经有序的数据。**

## 选择排序 ##

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 7][]

也比较简单，直接看代码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 8][]

## 扩展 ##

**冒泡排序和插入排序的时间复杂度都是 O(n2)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？**

解答：从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。我们来看这段操作：

冒泡排序中数据的交换操作：
    if (a[j] > a[j+1]) { // 交换
       int tmp = a[j];
       a[j] = a[j+1];
       a[j+1] = tmp;
       flag = true;
    }
    
    插入排序中数据的移动操作：
    if (a[j] > value) {
      a[j+1] = a[j];  // 数据移动
    } else {
      break;
    }

我们把执行一个赋值语句的时间粗略地计为单位时间（unit\_time），然后分别用冒泡排序和插入排序对同一个逆序度是 K 的数组进行排序。用冒泡排序，需要 K 次交换操作，每次需要 3 个赋值语句，所以交换操作总耗时就是 3\*K 单位时间。而插入排序中数据移动操作只需要 K 个单位时间。

**这个只是我们非常理论的分析**，为了实验，针对上面的冒泡排序和插入排序的 Java 代码，我写了一个性能对比测试程序，随机生成 10000 个数组，每个数组中包含 200 个数据，然后在我的机器上分别用冒泡和插入排序算法来排序，**冒泡排序算法大约 555ms** 才能执行完成，而**插入排序只需要 115ms** 左右就能搞定！

## 总结 ##

要想分析、评价一个排序算法，需要从执行效率、内存消耗和稳定性三个方面来看。这三种时间复杂度是 O(n2) 的排序算法，冒泡排序、插入排序、选择排序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 9][]

## 推荐阅读 ##

*  [如果你还对面试常问的缓存击穿、缓存穿透和缓存雪崩不了解，那么你一定得看看][Link 1]
 *  [面试必问的Redis集群-官方推荐方案RedisCluster][Redis_-_RedisCluster]
 *  [Redis哨兵机制-面试你不得不了解的知识点][Redis_-]

最近面试 字节、BAT，整理一份面试资料《Java 面试 BAT 通关手册》，覆盖了 Java 核心技术、JVM、Java 并发、SSM、微服务、数据库、数据结构等等。获取方式：点“在看”，关注公众号并回复 666 领取，更多内容陆续奉上

![format_png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70]: /images/20230528/afd88e37c747427ab3c17dd27f2b1b6f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 1]: /images/20230528/fa4e8e0b5ac340b983b752303832ce14.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 2]: /images/20230528/731fd23132ec4270ab8d228680501699.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 3]: /images/20230528/beb5aa4d3f604490a05dc0047575c72d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 4]: /images/20230528/de0df98b62f84d8c80a18efca888224f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 5]: /images/20230528/686d02bcba2144eb84e6a82601fce379.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 6]: /images/20230528/000be6f615704d0ea02b6593816a5d79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 7]: /images/20230528/831f919d00aa43269adcbe9b7f030836.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 8]: /images/20230528/7ada5b56d577409585fe182de4b6d829.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RhdXJ1c183Yw_size_16_color_FFFFFF_t_70 9]: /images/20230528/2c4324a36439447b8cf28a2cbfbb8727.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzA4MTE4NTg1OA==&mid=2247483912&idx=1&sn=b2819669539f8b37d15e7e978b77e8f1&chksm=9f999f25a8ee16337e99e02b3dfb2a6854b54e05dddc0b6b895d37a4e59a15671dd9bdcd2bf7&scene=21#wechat_redirect
[Redis_-_RedisCluster]: http://mp.weixin.qq.com/s?__biz=MzA4MTE4NTg1OA==&mid=2247483907&idx=1&sn=3d3385b33b0c66023f54fa0a556ee7b0&chksm=9f999f2ea8ee1638c9cb8ed3a611680e4b7f4cd5c34a1f0b39d37ae22ef0398ff53eecacab53&scene=21#wechat_redirect
[Redis_-]: http://mp.weixin.qq.com/s?__biz=MzA4MTE4NTg1OA==&mid=2247483889&idx=1&sn=51aa27477e038a90c5b50080f5a1daa1&chksm=9f999cdca8ee15ca7b8533061aad3dd0f16a86b9930c6672dd9ee53459531d303c49cb39d874&scene=21#wechat_redirect
[format_png]: /images/20230528/4c619894e3b54d40bd80ab23afea187e.png