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

3,359 阅读4分钟

对于任何一个程序员来说,学习的第一个算法,可能就是排序。最常用的有:冒泡排序、计数排序、插入排序、快速排序、选择排序等。 其中:冒泡排序、插入排序、选择排序的时间复杂度为O(n^2),且是基于比较的排序算法。

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

如何分析一个"排序算法"

学习排序算法,除了学习他的算法原理、代码实现之外,更重要的是要学会如何评价、分析一个排序算法。分析一个排序算法,一般从下面几个方面入手:

排序算法的执行效率

  1. 最好情况、最坏情况、平均情况时间复杂度
  2. 时间复杂度的系数、常数、低阶
  3. 比较次数和交换(或移动)次数(排序算法的内存消耗,排序算法的稳定性)

冒泡排序解析

一、冒泡排序是原地排序算法吗?

冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为O(1),是一个原地排序算法。

二、冒泡排序是稳定的排序算法吗?

在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。

三、冒泡排序的时间复杂度是多少?

最好情况下,要排序的数据已经是有序的了,我们只需要进行一次冒泡操作,就可以结束了,所以最好情况时间复杂度是O(n)。而最坏的情况是,要排序的数据刚好是倒序排列的,我们需要进行n次冒泡操作,所以最坏情况时间复杂度为O(n^2)

插入排序解析

一、插入排序是原地排序算法吗?

从实现过程可以明显看出,插入排序算法的运行并不需要额外的存储空间,所以它的空间复杂度为O(1),是一个原地排序算法。

二、插入排序是稳定的排序算法吗?

在插入排序中,对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序的稳定的排序算法。

三、插入排序的时间复杂度是多少?

如果要排序的数据已经是有序的,我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置,每次只需要比较一个数据就能确定插入的位置。所以这种情况下,最好的时间复杂度为O(n)。

如果数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据,所以最坏的事件复杂度为O(n^2).

冒泡排序和插入排序的时间复杂度都是O(n^2),都是原地排序算法,为什么插入排序要比冒泡排序更受欢迎呢?

从前面的分析可以得出:冒泡排序不管怎么优化,元素交换的次数是一个固定值,就是原始数据的逆序度。插入排序是同样的,不管怎么优化,元素移动的次数也等于原始数据的逆序度。

但是从代码实现上来看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要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] // 数据移动
}

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

总结:

所以,虽然冒泡排序和插入排序在时间复杂度上都是一样的,都是O(n^2),但如果我们希望把性能做到极致,那肯定首选插入排序。当然,插入排序的算法思路也有很大的优化空间,因此又出现了希尔排序