冒泡排序和插入排序

冒泡排序和插入排序

困而学,学而知

自从二分查找算法文章以来,没有更新新的算法文章了,今天就来说说冒泡排序和插入排序算法。本文决定先从什么是排序算法入手,再到各位耳熟能详的冒泡排序,最后再到插入排序

排序算法

不管是做什么语言开发,排序算法应该是最开始接触的算法了。同时,排序算法也无处不在,比如本站首页的博客就是创建时间倒序排序(最新创建在最前面)。当然了,这是MySQL数据库的排序算法,可能并不是我们今天要讲的插入排序。排序算法有很多,我们常听到的有冒泡排序、选择排序、插入排序、快速排序、归并排序和希尔排序等,也有我们几乎没有听过的猴子排序、睡眠排序、面条排序等。虽然有这么多算法,但是只要能够掌握常用的就好了。

掌握了这些算法,不仅对我们的编码能力有提高,对我们阅读源码也有很大的帮组。

要来说排序算法,肯定要从时间复杂度和空间复杂度来分析,从这两个角度来分析算法,我们可以分析出算法的优缺点。我们在算法复杂度分析有讲如何来分析算法的。但是上面也说了有这么多算法,我们不可能一个一个的来分析。所以我们先来对排序算法的复杂度来一个纵览。

排序算法的时间复杂度

我们可以看到冒泡排序和插入排序的时间复杂度其实是一样的。但其实在实际开发中,我们更加推荐插入排序,而不是冒泡排序,这又是为什么呢?我们在后面的文章中慢慢揭晓。

冒泡排序

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

要说冒泡排序,我们还是先从一个例子入手来分析过程。我们要对一组数据 4,5,6,3,2,1,从小到大进行排序。第一次冒泡操作的详细过程就是这样:

第一次冒泡排序

可以看到,第一次冒泡结束之后,数组中最大的数6就已经在数组的最后一个位置上面了。我们从第1次冒泡可以推断出,如果要对整个数组进行冒泡排序,需要经过6次冒泡,具体6次冒泡的过程如下:

冒泡排序过程

知道了冒泡算法是什么,我们现在来看看,冒泡算法的实现:(Java)

 public int[] bubbleSort(int[] origin) {
  
   for (int i = 1; i < result.length; i++) {
			boolean flag = false; // 提前退出循环标志
     for (int j = 0; j < result.length - i; j++) {
       if (result[j] > result[j + 1]) {
         int temp = result[j];
         result[j] = result[j + 1];
         result[j + 1] = temp;
         flag = true;
       }
     }
     if (!flag){
       break; // 没有数据交换,提前退出
     }
   }
   return result;
 }

上图的flag,是提前退出冒泡标志。我们通过这个标志来优化冒泡排序,如果当一次冒泡已经达到有序了,那么下次再冒泡的时候,就会退出循环。

从上面的算法分析和代码实现,我们可以计算出,冒泡算法最好时间复杂度(只有一次冒泡)是O(n),而最坏时间复杂度(有6次排序)是O(n2),平均时间复杂度为O(n2)。和我们上图排序算法的时间复杂度的是一样的。

插入排序

如果我们想要想一个有序的数组中插入一条数据,并且还是需要保持数组的有序性,那我们改怎么做呢?

我们会遍历有序数组,找到合适的位置插入进去,这种一个动态排序的过程,即动态地往有序集合中添加数据。

插入排序也利用了上面的思想,插入排序将数组分为两个区间,已排序区间和待排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取待排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到待排序区间中元素为空,算法结束。

上面冒泡排序算法的数组不能直观的体现, 所以我们换一个数组: 4,6,5,2,4,1,3。数组使用插入排序的过程如下:

插入排序的过程分析

上图可以看到插入排序的算法逻辑,话不多说,我们直接来找实现一个插入排序。

public static void main(String[] args) {
  int[] array = new int[]{4, 6, 5, 2, 4, 1, 3};
  InsertSort.insertSort(array);
}
private static void insertSort(int[] array) {
  for (int i = 1; i < array.length; i++) {
    int value = array[i];
    int j = i - 1;
    for (; j >= 0; j--) {
      if (array[j] > value) {
        array[j + 1] = array[j]; // 数据移动
      } else { break; }
    }
    array[j + 1] = value;
    System.out.println(Arrays.toString(array));
  }
}

我们来看看输出

插入排序输出

看看这个输入是不是和上面分析的图差不多呢?图[插入排序算法分析]比输出要多一行,这多的一行是插入排序的初始已排序和未排序区间。

插入排序的算法复杂度

从插入排序算法的分析图和插入排序的代码片段,我们可以分析出插入排序最好时间复杂度是O(n),而最坏时间复杂度是O(n2),平均时间复杂度为O(n2)。

既然插入排序和冒泡排序算法时间复杂度一样,那为什么在实际开发中为什么建议使用插入排序是不是冒泡排序。下面我们就来解答一下。

还有一个点就是插入排序和冒泡排序是都是不管怎么优化,元素移动的次数也等于原始数据的逆序度。

冒泡排序和插入排序的比较

本文开头的时候,我们提出了一个疑问,既然插入排序和冒泡排序算法时间复杂度一样,那为什么在实际开发中为什么建议使用插入排序是不是冒泡排序。

其实我们在评价一个排序算法的性能的时候,我们不只是看他的时间复杂度(最好、最坏、平均),同时也会考虑到时间复杂度的系数、常数和低阶,也会看排序数组的大小,比较次数和交换(或移动)次数。

时间复杂度的系数、常数和低阶

怎么说要考虑到时间复杂度的系数、常数和低阶。虽然我们在分析算法的复杂度的时候,是忽略了系数、常数和低阶的。但是如果数据量比较大的情况下,这些因素也会影响到时间复杂度的性能。

比如一个忽略了系数、常数和低阶的算法的时间复杂度是O(n2),但他实际的时间复杂度为O(2n2 + 2n + 100)。10个数据量的情况下,可能差别不是很大,但是在1000个、1000000个的数据量下,差个的差别就会很大,所以,在考虑一个插入排序的复杂度是时候,也需要把这些考虑进去。

比较次数和交换(或移动)次数

基于比较的排序算法,会涉及到两个操作:一种是元素比较大小,另一种是元素交换或移动。所以在评价一个排序算法的性能的时候,也会比较次数和交换次数计算进去。同时,为了能够更好的量化这两个比较规则,引入了两个概念:原地排序和稳定性。

原地排序

原地排序算法,就是特指空间复杂度是 O(1) 的排序算法。

怎么说呢,就是比如说,这个排序算法对数组排序前序前后,不会占用额外内存空间。

稳定性

稳定性。这个概念是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

分析冒泡排序和插入排序

我们先从比较次数和交换次数来分析两个算法。

不管是冒泡排序和插入排序,在排序前后,只涉及到元素的交换和移动,并没有涉及到申请额外的内容空间,所以,冒泡排序和插入排序都是原地排序算法。

在稳定性方面,虽然冒泡排序涉及到元素的交换,只要我们交换元素的时候,如果两个元素值相等,我们不做交换,这时候我们也可以说冒泡排序算法是稳定的排序算法。

而插入排序,我们也可以选择在两个元素相等的时候,不做插入操作,这样也可以保证插入排序是一个稳定的排序算法。

从时间复杂度方面,我们上面的内容中已经解答了,所以这里就不解答了。

但到了这里我们还是没有解释开篇的问题呀,不急,下面就来解释了。

插入 优于 冒泡

我们可以从上面的代码中找出端倪

// 冒泡排序
 if (result[j] > result[j + 1]) {
   int temp = result[j];
   result[j] = result[j + 1];
   result[j + 1] = temp;
   
 }
// 插入排序
if (array[j] > value) {
  array[j + 1] = array[j]; // 数据移动
} else { break; }

可以看到冒泡排序的数据交换要比插入排序的数据移动要复杂很多(即使是从代码的行数)。

我们把执行一个赋值语句的时间粗略地计为单位时间(unit_time),然后分别用冒泡排序和插入排序对同一个逆序度是 K 的数组进行排序。用冒泡排序,需要 K 次交换操作,每次需要 3 个赋值语句,所以交换操作总耗时就是 3*K 单位时间。而插入排序中数据移动操作只需要 K 个单位时间。也就是说对已同一个数组,插入排序算法的执行时间要比冒泡排序快很多。我写了一个比较demo,看一下两个算法在统一环境下的耗时。

List<int[]> list = new ArrayList<>();
// 定义1000个数组,每个数组200个数据
for (int i = 0; i < 1000; i++) {
  int[] arr = new int[200];
  for (int j = 0; j < arr.length; j++) {
    arr[j] = new Random(100).nextInt();
  }
  list.add(arr);
}
long start = System.currentTimeMillis();
// 冒泡排序
for (int[] a : list) {
  BubbleSort.bubbleSort(a);
}
System.out.format("冒泡排序耗时: %s ms\n", System.currentTimeMillis() - start);
start = System.currentTimeMillis();
for (int[] a : list) {
  InsertSort.insertSort(a);
}
System.out.format("插入排序排序耗时: %s ms\n", System.currentTimeMillis() - start);

来看看上面代码片段的输出:

可以看到,同样的环境和数据量的情况下,冒泡排序的耗时是插入排序的8倍。所以如果我们要在实际开发中将性能优化到极致,还是比较推荐插入排序。

简单总结一下,本节从数据的比较和交换次数,时间复杂度的系数、常数和低阶两个方面来比较分析了冒泡排序和插入排序,也从代码角度来说明了实际开发中因为执行时间的目的而插入排序由于冒泡排序。

本文总结

本文注重讲了冒泡排序和插入排序,讲了两个算法核心逻辑已经代码实现。同时也映入两个评价排序算法性能的规则,我们可以这里两个规则评价排序算法的性能,这两个规则也会在后续将排序算法中也会继续用这两个规则来评价排序算法的性能。

同时,本文的内容算是看了极客时间专栏数据结构与算法之美的一个学习总结,如果各位有需求,可以去极客时间看看。很推荐,写得很好。

参考文献

数据结构与算法之美

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://baozi.fun/archives/bubble-insert-sort

Buy me a cup of coffee ☕.