冒泡排序,你需要了解的三种优化

在这里插入图片描述

冒泡排序，顾名思义就像水沸腾时，沸腾的水泡自下而上，由大到小的往水面沸腾.

从大一接触唐浩强爷爷的C语言，老师讲的第一个排序算法便是冒泡排序.
在这里插入图片描述

# 一、冒泡思想

冒泡排序是交换排序的一种，在基础排序算法中还有快速排序 (opens new window).

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序有误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名“冒泡排序”.

在这里插入图片描述

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法演示

在这里插入图片描述

排序动画过程解释

将天平放在序列的右端，并比较天平左右的数字
在这种情况下我们比较 3 和 8
比较后如果右边的数字较小，则被交换
因为 8 大于 3 ，所以数字不用交换
比较完成后，将天平向左移动一个位置，比较数字
因为 3 大于 2 ，所以数字不用交换
比较完成后，逐一移动天平，比较数字
此时 2 小于 4 ，所以左右的数字互相交换
重复同样的操作，直到天平移动到左端
。。。。。。
天平到达左端
经过上述的操作，数列中最小的数字已经移动到左端
将天平返回右端
重复相同的操作，直到所有数字都被排序

以上动画演示及详细解释来源于微型公众号【五分钟学算法 (opens new window)】，很多基础的排序算法和数据结构动图解释的很清楚，推荐一波

# 二、冒泡实现及优化

通过以上的讲解，相信大家对冒泡排序的思维有一定的了解。我们通过一个简单的例子，用代码来实现我们通过这8个数从小到大来排序：在这里插入图片描述

在这里插入图片描述

【数据结构和算法动态可视化网站】 (opens new window)，动图演示很形象具体

代码使用双层循环进行排序

外部循环控制每轮排序元素的个数，即参与冒泡的元素个数
内部循环实现每一轮的冒泡处理，即每轮的排序趟数。先进行元素比较，再进行元素交换

排序过程详解：

n个元素，进行n - 1轮排序

每轮排序的趟数为参与此轮排序的元素个数

# 1. 基础版本

 /**
   * @自下往上冒泡
   * 由小到大排序
   * @param arr
   */
  public static void bubbleSort_toLarge(int[] arr) {
      int len = arr.length - 1;
      //待排序元素个数 n - 1, 剩下最后一个元素默认有序了
      for (int i = len; i > 0; i--) {
          //每轮排序趟数
          for (int j = 0; j < i; j++) {
              if(arr[j] > arr[j+1] ) {
                  int temp = arr[j];
                  arr[j] = arr[j+1];
                  arr[j+1] = temp;
              }
          }
      }
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在这里插入图片描述自下往上冒泡-----由大到小排列

 /**
   * @自上往下冒泡
   * 由大到小排序
   * @param arr
   */
  public static void bubbleSort_toSmall(int[] arr) {
      int len = arr.length - 1;
      for (int i = 0; i < len; i++) {
          for (int j = 0; j < len - i; j++) {
              if(arr[j] < arr[j+1] ) {
                  int temp = arr[j];
                  arr[j] = arr[j+1];
                  arr[j+1] = temp;
              }
          }
      }
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在这里插入图片描述

# 2. 升级版本

那碰到这样的数列，或者直接就是有序的数列，那排序的效率岂不是很低？我只需要一轮冒泡就完成了排序，但是依然得全走一遍

与基础版本相比较，升级版本利用flag作为标记。

在内层每一轮的排序中，如果有元素发生了交换，则flag = true，说明数列无序；

如果元素有序，此时flag为false，!flag为 true，证明此时数列已经有序了，则冒泡排序结束

public static int[] bubble(int[] arr) {
    int len = arr.length;
    //待排序元素个数 n - 1
    for (int i = len - 1; i > 0; i--) {
        //重置flag,进行本次判断，默认此轮排序无序
        boolean flag = false;
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        //此趟排序没有进行数值交换,flag = false
        if (!flag)
            break;
    }
    return arr;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

break跳出的是外层循环，即满足条件，则排序结束！

第一轮循环将6沉底后，开始第二轮循环
在第二轮循环中，由于元素有序，不进入到for(int j = 0; j < i; j++)，所以flag = false
此时，直接break出外层for(int i = len-1; i > 0; i--)循环。因为冒泡是逐个比较的，发现在第二轮的循环中，两两比较均符合有序，==说明整个数列此时已经有序了==
break跳出外层循环，结束排序即可我们再换一个新的数列，它的前半部分无序（3，4，2，1），后半部分有序（5，6，7，8），并且后半部分的最小值也大于前半部分的最大值，就是只用排前半部分就好了，直接把它放到后半部前面就好。

在这里插入图片描述此时，还用版本2的升级版也做了一半的无用功，还有待需要继续优化

挤牙膏，高极版的来了...

在这里插入图片描述每次排序前或排序后数组的后面都有一部分已经有序，这时我们只要记下最后一次排序的数组的下标，下次排序的时候就可以只排序到此下标位置即可，因为后面的已经有序了。

# 3. 高级版

/**
 * @Author: Mr.Q
 * @Date: 2020-04-09 16:12
 * @Description:标志位该进版，针对一半有序一半无序
 * { 3, 4, 2, 1, 5, 6, 7, 8 }
 */
public static int[] bubble(int[] arr) {
    for (int i = arr.length - 1; i > 0; i--) {
        //初始化border，让 border - 1 <= 0 即可
        int border = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                //3  4  2  1  5[border]  6  7  8 待排序元素个数为(j+1)个
                border = j + 1;
            }
        }
        //更新待排序元素的边界,下一次比较到记录位置即可
        i = border;
    }
    return arr;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

因为此时后半段数列有序，当把元素4放到5之前时，border = 3，后面便不再比较

这样，相对于上一个版本，针对这种半有序，半无序的数列效率又有提高了不少呢！

在这里插入图片描述这次，我要排这个呢？好像上面的效率又不行了... 上面的 版本3--高级版 其实就可以了，但是，针对此还有一中特定的排序算法（谁发明的，此时我要膜拜三分钟）

# 4. 鸡尾酒排序

鸡尾酒排序 (opens new window)

冒泡排序的每一轮都是从左到右来比较元素，是单向的位置交换；

但是，鸡尾酒排序元素比较和交换是双向的

排序过程如下：

第1趟：

和基础冒泡排序一样，从左到右走一趟，把8沉底

在这里插入图片描述 第2趟：

从右往左冒泡（从倒数第二位开始）

在这里插入图片描述

第3趟：

继续从左向右走（虽然有序，但继续判断，类似于最基础的冒泡）

第4趟：

从右往左（从倒数第三位开始）

直到没有元素再发生交换而结束

public static int[] cocktailSort(int[] arr) {
    for (int i = 0; i < arr.length / 2; i++) {
        boolean flag = false;
        //奇数轮,从左向右比较交换
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                //此趟排序没有进行数值交换
                flag = true;
            }
        }
        //在一趟排序中没有发生过交换
        if (!flag)
            break;
        //偶数轮,从右向左比较交换
        for (int j = arr.length - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                //此趟排序没有进行数值交换
                flag = true;
            }
        }
        //在一趟排序中没有发生过交换
        if (!flag)
            break;
    }
    return arr;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

在这里插入图片描述 鸡尾酒排序与冒泡排序不同的地方

鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的性能，原因是冒泡排序只从一个方向进行比对（由低到高），每次循环只移动一个项目。但是，鸡尾酒排序元素比较和交换是双向的。

《被排序算法吊打系列汇总》

【参考文章】

编辑

上次更新: 2021/06/27, 10:49:09

← 被排序算法吊打系列选择排序→