资讯专栏INFORMATION COLUMN

你知道和你不知道的冒泡排序

Worktile / 2494人阅读

摘要:用来标示该轮冒泡排序中,数组是否是有序的。适用情况当冒泡算法运行到后半段的时候,如果此时数组已经有序了,需要提前结束冒泡排序。当第一轮冒泡排序结束后,元素会被移动到下标的位置。

这篇文章包含了你一定知道的,和你不一定知道的冒泡排序。

gif看不了可以点击【原文】查看gif。

源码: 【地址】

1. 什么是冒泡排序

可能对于大多数的人来说比如我,接触的第一个算法就是冒泡排序。

我看过的很多的文章都把冒泡排序描述成我们喝的汽水,底部不停的有二氧化碳的气泡往上冒,还有描述成鱼吐泡泡,都特别的形象。

其实结合一杯水来对比很好理解,将我们的数组竖着放进杯子,数组中值小的元素密度相对较小,值大的元素密度相对较大。这样一来,密度大的元素就会沉入杯底,而密度小的元素会慢慢的浮到杯子的最顶部,稍微专业一点描述如下。

冒泡算法会运行多轮,每一轮会依次比较数组中相邻的两个元素的大小,如果左边的元素大于右边的元素,则交换两个元素的位置。最终经过多轮的排序,数组最终成为有序数组。
2. 排序过程展示

我们先不聊空间复杂度和时间复杂度的概念,我们先通过一张动图来了解一下冒泡排序的过程。

这个图形象的还原了密度不同的元素上浮和下沉的过程。

3. 算法V1 3.1 代码实现
private void bubbleSort(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        exchange(arr, j, j + 1);
      }
    }
  }
}

private void exchange(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]
3.2 实现分析

各位大佬看了上面的代码之后先别激动,坐下坐下,日常操作。可能很多的第一个冒泡排序算法就是这么写的,比如我,同时还自我感觉良好,觉得算法也不过如此。

我们还是以数组[5, 1, 3, 7, 6, 2, 4]为例,我们通过动图来看一下过程。

思路很简单,我们用两层循环来实现冒泡排序。

第一层,控制冒泡排序总共执行的轮数,例如例子数组的长度是7,那么总共需要执行6轮。如果长度是n,则需要执行n-1轮

第二层,负责从左到右依次的两两比较相邻元素,并且将大的元素交换到右侧

这就是冒泡排序V1的思路。

下表是通过对一个0-100000的乱序数组的标准样本,使用V1算法进行排序所总共执行的次数,以及对同一个数组执行100次V1算法的所花的平均时间。

算法执行情况 结果
样本 [0 - 100000] 的乱序数组
算法 V1 执行的总次数 99990000 次(9999万次
算法 V1 运行 100 次的平均时间 181 ms
4. 算法V2 4.1 实现分析

仔细看动图我们可以发现,每一轮的排序,都从数组的最左端再到最右。而每一轮的冒泡,都可以确定一个最大的数,固定在数组的最右边,也就是密度最大的元素会冒泡到杯子的最上面。

还是拿上面的数组举例子。下图是第一轮冒泡之后数组的元素位置。

第二轮排序之后如下。

可以看到,每一轮排序都会确认一个最大元素,放在数组的最后面,当算法进行到后面,我们根本就没有必要再去比较数组后面已经有序的片段,我们接下来针对这个点来优化一下。

4.2 代码实现

这是优化之后的代码。

private void bubbleSort(int[] arr) {
  for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        exchange(arr, j, j + 1);
      }
    }
  }
}

private void exchange(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]

优化之后的实现,也就变成了我们动图中所展示的过程。

每一步之后都会确定一个元素在数组中的位置,所以之后的每次冒泡的需要比较的元素个数就会相应的减1。这样一来,避免了去比较已经有序的数组,从而减少了大量的时间。

算法执行情况 结果
样本 [0 - 10000] 的乱序数组
算法 V2 执行的总次数 49995000 次(4999万次
算法 V2 运行 100 次的平均时间 144 ms
运行时间与 V1 对比 V2 运行时间减少 20.44 %
执行次数与 V1 对比 V2 运行次数减少 50.00 %

可能会有人看到,时间大部分已经会觉得满足了。从数据上看,执行的次数减少了50%,而运行的时间也减少了20%,在性能上已经是很大的提升了。而且已经减少了7亿次的执行次数,已经很NB了。 那是不是到这就已经很完美了呢?

答案是No

4.3 哪里可以优化

同理,我们还是拿上面长度为7的数组来举例子,只不过元素的位置有所不同,假设数组的元素如下。

[7, 1, 2, 3, 4, 5, 6]

我们再来一步一步的执行V2算法, 看看会发生什么。

第一步执行完毕后,数组的情况如下。

继续推进,当第一轮执行完毕后,数组的元素位置如下。

这个时候,数组已经排序完毕,但是按照目前的V2逻辑,仍然有5轮排序需要继续,而且程序会完整的执行完5轮的排序,如果是100000轮呢?这样将会浪费大量的计算资源。

5. 算法V3 5.1 代码实现
private void bubbleSort(int[] arr) {
  for (int i = 0; i < arr.length - 1; i++) {
    boolean flag = true;
    for (int j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = false;
        exchange(arr, j, j + 1);
      }
    }
    if (flag) {
      break;
    }
  }
}

private void exchange(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]
5.2 实现分析

我们在V2代码的基础上,在第一层循环,也就是控制总冒泡轮数的循环中,加入了一个标志为flag。用来标示该轮冒泡排序中,数组是否是有序的。每一轮的初始值都是true。

当第二层循环,也就是冒泡排序的元素两两比较完成之后,flag的值仍然是true,则说明在这轮比较中没有任何元素被交换了位置。也就是说,数组此时已经是有序状态了,没有必要再执行后续的剩余轮数的冒泡了。

所以,如果flag的值是true,就直接break了(没有其他的操作return也没毛病)。

算法执行情况 结果
样本 [0 - 10000] 的乱序数组
算法 V3 执行的总次数 49993775
算法 V3 运行 100 次的平均时间 142 ms
运行时间与 V2 对比 V3 运行时间减少 00.00 %
执行次数与 V2 对比 V3 运行次数减少 00.00 %
5.3 数据分析

大家看到数据可能有点懵逼。

你这个优化之后,运行时间执行次数都没有减少。你这优化的什么东西?

其实,这就要说到算法的适用性了。V3的优化是针对原始数据中存在一部分或者大量的数据已经是有序的情况,V3的算法对于这样的样本数据才最适用。

其实是我们还没有到优化这种情况的那一步,但是其实仍然有这样的说法,面对不同的数据结构,几乎没有算法是万能的

而目前的样本数据仍然是随机的乱序数组,所以并不能发挥优化之后的算法的威力。所谓对症下药,同理并不是所有的算法都是万能的。对于不同的数据我们需要选择不同的算法。例如我们选择[9999,1,2,…,9998]这行的数据做样本来分析,我们来看一下V3算法的表现。

算法执行情况 结果
样本 [0 - 10000] 的乱序数组
算法 V3 执行的总次数 19995
算法 V3 运行 100 次的平均时间 1 ms
运行时间与 V3 乱序样例对比 V3 运行时间减少 99.96 %
执行次数与 V3 乱序样例对比 V3 运行次数减少 99.29 %

可以看到,提升非常明显。

5.4 适用情况

当冒泡算法运行到后半段的时候,如果此时数组已经有序了,需要提前结束冒泡排序。V3针对这样的情况就特别有效。

6. 算法V4

嗯,什么?为什么不是结束语?那是因为还有一种没有考虑到啊。

6.1 适用情况总结

我们总结一下前面的算法能够处理的情况。

V1:正常乱序数组

V2:正常乱序数组,但对算法的执行次数做了优化

V3:大部分元素已经有序的数组,可以提前结束冒泡排序

还有一种情况是冒泡算法的轮数没有执行完,甚至还没有开始执行,后半段的数组就已经有序的数组,例如如下的情况。

这种情况,在数组完全有序之前都不会触发V3中的提前停止算法,因为每一轮都有交换存在,flag的值会一直是true。而下标2之后的所有的数组都是有序的,算法会依次的冒泡完所有的已有序部分,造成资源的浪费。我们怎么来处理这种情况呢?

6.2 实现分析

我们可以在V3的基础之上来做。

当第一轮冒泡排序结束后,元素3会被移动到下标2的位置。在此之后没有再进行过任意一轮的排序,但是如果我们不做处理,程序仍然会继续的运行下去。

我们在V3的基础上,加上一个标识endIndex来记录这一轮最后的发生交换的位置。这样一来,下一轮的冒泡就只冒到endIndex所记录的位置即可。因为后面的数组没有发生任何的交换,所以数组必定有序。

6.3 代码实现
private void bubbleSort(int[] arr) {
  int endIndex = arr.length - 1;
  for (int i = 0; i < arr.length - 1; i++) {
    boolean flag = true;
    int endAt = 0;
    for (int j = 0; j < endIndex; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = false;
        endAt = j;
        exchange(arr, j, j + 1);
      }
    }
    endIndex = endAt;
    if (flag) {
      break;
    }
  }
}

private void exchange(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]
7. 算法V5

这一节仍然不是结束语...

7.1 算法优化

我们来看一下这种情况。

对于这种以上的算法都将不能发挥其应有的作用。每一轮算法都存在元素的交换,同时,直到算法完成以前,数组都不是有序的。但是如果我们能直接从右向左冒泡,只需要一轮就可以完成排序。这就是鸡尾酒排序,冒泡排序的另一种优化,其适用情况就是上图所展示的那种。

7.2 代码实现
private void bubbleSort(int[] arr) {
  int leftBorder = 0;
  int rightBorder = arr.length - 1;

  int leftEndAt = 0;
  int rightEndAt = 0;

  for (int i = 0; i < arr.length / 2; i++) {
    boolean flag = true;
    for (int j = leftBorder; j < rightBorder; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = false;
        exchange(arr, j, j + 1);
        rightEndAt = j;
      }
    }
    rightBorder = rightEndAt;
    if (flag) {
      break;
    }

    flag = true;
    for (int j = rightBorder; j > leftBorder; j--) {
      if (arr[j] < arr[j - 1]) {
        flag = false;
        exchange(arr, j, j - 1);
        leftEndAt = j;
      }
    }
    leftBorder = leftEndAt;
    if (flag) {
      break;
    }
  }
}

private void exchange(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int[] arr = new int[]{2, 3, 4, 5, 6, 7, 1};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]
7.3 实现分析

第一层循环同样用于控制总的循环轮数,由于每次需要从左到右再从右到左,所以总共的轮数是数组的长度 / 2。

内存循环则负责先实现从左到右的冒泡排序,再实现从右到左的冒泡,并且同时结合了V4的优化点。

我们来看一下V5与V4的对比。

算法执行情况 结果
样本 [2,3,4…10000,1] 的数组
算法 V5 执行的总次数 19995
算法 V5 运行 100 次的平均时间 1 ms
运行时间与 V4 对比 V5 运行时间减少 99.97 %
执行次数与 V4 对比 V5 运行次数减少 99.34 %
8. 总结

以下是对同一个数组,使用每一种算法对其运行100次的平均时间和执行次数做的的对比。

[0 - 10000] 的乱序数组 V1 V2 V3 V4 V5
执行时间(ms) 184 142 143 140 103
执行次数(次) 99990000 49995000 49971129 49943952 16664191
大部分有序的情况 V1 V2 V3 V4 V5
执行时间(ms) 181 141 146 145 107
执行次数(次) 99990000 49995000 49993230 49923591 16675618

而冒泡排序的时间复杂度分为最好的情况和最快的情况。

最好的情况为O(n). 也就是我们在V5中提到的那种情况,数组2, 3, 4, 5, 6, 7, 1。使用鸡尾酒算法,只需要进行一轮冒泡,即可完成对数组的排序。

最坏的情况为O(n^2).也就是V1,V2,V3和V4所遇到的情况,几乎大部分数据都是无序的。

往期文章:

聊聊微服务集群当中的自动化工具

go源码解析-Println的故事

用go-module作为包管理器搭建go的web服务器

WebAssembly完全入门——了解wasm的前世今身

小强开饭店-从单体应用到微服务

相关:

微信公众号: SH的全栈笔记(或直接在添加公众号界面搜索微信号LunhaoHu)

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/74993.html

相关文章

  • 知道javascript事件

    摘要:然而和分别提出了完全相反的的概念事件冒泡和事件捕获。所有的节点中包含了这两个方法,它们都接受个参数要处理的事件名作为事件处理程序的函数和一个布尔值。事件流级事件规定的事件流包括三个阶段事件捕获阶段处于目标阶段事件冒泡阶段。 事件流描述的是从页面中接受事件的顺序。然而ie和netscape分别提出了完全相反的的概念:事件冒泡和事件捕获。下面就说说这两种事件流: 事件冒泡 事件冒泡,就是说...

    imtianx 评论0 收藏0
  • 知道javascript事件

    摘要:然而和分别提出了完全相反的的概念事件冒泡和事件捕获。所有的节点中包含了这两个方法,它们都接受个参数要处理的事件名作为事件处理程序的函数和一个布尔值。事件流级事件规定的事件流包括三个阶段事件捕获阶段处于目标阶段事件冒泡阶段。 事件流描述的是从页面中接受事件的顺序。然而ie和netscape分别提出了完全相反的的概念:事件冒泡和事件捕获。下面就说说这两种事件流: 事件冒泡 事件冒泡,就是说...

    marek 评论0 收藏0
  • PHP面试:尽可能多说出知道排序算法

    摘要:良好的排序算法具有进行最少的比较和交换的特征。冒泡排序是一个基于比较的排序算法,被认为是效率最低的排序算法之一。现在让我们使用实现冒泡排序算法。插入排序到目前为止,我们已经看到了两种基于比较的排序算法。 预警 本文适合对于排序算法不太了解的新手同学观看,大佬直接忽略即可。因为考虑到连贯性,所以篇幅较长。老铁们看完需要大概一个小时,但是从入门到完全理解可能需要10个小时(哈哈哈,以我自己...

    objc94 评论0 收藏0
  • 数据结构与算法——冒泡排序

    摘要:多练练排序算法,不仅能够让我们知道一些排序方法的底层实现细节,更能够锻炼我们的思维,提升编程能力。排序算法的稳定性一个稳定的排序,指的是在排序之后,相同元素的前后顺序不会被改变,反之就称为不稳定。 1. 导言 因为这是排序算法系列的第一篇文章,所以多啰嗦几句。 排序是很常见的算法之一,现在很多编程语言都集成了一些排序算法,比如Java 的Arrays.sort()方法,这种方式让我们可...

    Yang_River 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<