为什么插入排序比冒泡排序更受欢迎？

1. 插入排序和冒泡排序的时间复杂度

插入排序和冒泡排序的时间复杂度相同，都是 O(n2)，在实际的软件开发里，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢？

2. 先看一下排序算法的几个概念

1.原地排序

原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) ,的排序算法；因为只需要定义变量来交互值，所以为O(1)。

2.排序算法的稳定性

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

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

两个 3 哪个在前，哪个在后有什么关系啊，稳不稳定又有什么关系呢？为什么要考察排序算法的稳定性呢？

比如说，我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，我们怎么来做呢？ 最先想到的方法是：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂。借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。为什么呢？ 稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，我们用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。

3. 冒泡排序（Bubble Sort）

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

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

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

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

具体代码如下所示：

ps:冒泡排序是原地排序，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。冒泡排序是稳定的排序算法因为我们判断的是>而不是>=。冒泡排序的时间复杂度最好就是有序的所以是O(n),而最坏就是反序的就是O(n2)。

4.插入排序（Insertion Sort）

一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？很简单，我们只要遍历数组，找到数据应该插入的位置将其插入即可。

这是一个动态排序的过程，即动态地往有序集合中添加数据，我们可以通过这种方法保持集合中的数据一直有序。而对于一组静态数据，我们也可以借鉴上面讲的插入方法，来进行排序，于是就有了插入排序算法。

那插入排序具体是如何借助上面的思想来实现排序的呢？首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。如图所示，要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。

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

插入排序代码实现如下

ps:插入排序是原地排序，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。插入排序是稳定的排序算法因为我们判断的是>而不是>=。插入排序的时间复杂度最好就是有序的所以是O(n),而最坏就是反序的就是O(n2)。

4.为什么插入排序比冒泡排序更受欢迎？

冒泡和插入排序最好时间复杂度和最坏时间复杂度都是O(n)和O(n2)，首先我们看一下冒泡排序当比对结果若前比后大则交换位置（从小到大排序时）因为需要交换位置所以需要进行三次赋值操作，而插入排序只需要一次赋值操作，假如我们设每次赋值所需要时间为time那么，冒泡每交换一次就是3*time，而插入则是time，可能在你觉得不就是三次赋值嘛，能消费多少性能，当然在数组排序量不大时，看不出来效果，当数组排序量很大呢？下面我们通过实际测试看看性能上的差距

假定一个需要排序的数组为50000，为了两个算法对比时数据的一致性，所以我们数组中的默认值都是从小到大排序的，而将他们全部变成从大到小时看看两种算法所消耗的时间。图一为测试代码插入排序的所需时间为图二，冒泡排序为图三。

当然实际上在50000的数据量时也不是差距很大，但是如果是更大的呢？如果实际开发中使用到排序在这两种算法之间进行选择的话，优先选择插入排序。