vlambda博客
学习文章列表

图解冒泡排序,鸡尾酒排序

冒泡排序基本思想

定义

冒泡排序的英文是bubblesort,它是一种基础的交换排序

原理

每次比较两个相邻的元素,将较大的元素交换至右端 (升序排序)

思路

相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换它们的位置;当一个元素小于或等于右侧相邻元素时,位置不变

案例分析

初始的无序数列 {5,8,6,3,9,2,1,7},希望对其升序排序

图解分析

在经过第一轮交换后,最大的数 9 冒泡到了最右边

图解冒泡排序,鸡尾酒排序

到此为止,所有元素都是有序的了,这就是冒泡排序的整体思路。

冒泡排序是一种稳定排序,值相等的元素并不会打乱原本的顺序。由于该排序算法的每一轮都要遍历所有元素,总共遍历(元素数量-1)轮,所以平均时间复杂度是O(n2)

代码实现

第 1 版代码

使用双循环进行排序。外部循环控制所有的回合,内部循环实现每一轮的冒泡处理,先进行元素比较,再进行元素交换。

public static void bubbleSort(int[] arr){
  if (arr == null || arr.length == 0return;
  for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - 1 -i; j++) {
      int tmp = 0;
      //升序排序>,降序排序<
      if (arr[j] > arr[j + 1]){
          tmp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = tmp;
      }
    }
  }
}

第 2 版小优化代码

仍以无序数列 {5,8,6,3,9,2,1,7}为例,我们发现在第 6 轮的时候,数列已经是有序了,但冒泡排序仍然进行了第7轮,可以做一个小优化,在外层循环设置一个哨兵标记isSorted,默认有序,内层循环如果发生交换,则仍为无序

图解冒泡排序,鸡尾酒排序
public static void bubbleSort(int[] arr){
  if (arr == null || arr.length == 0return;
  for (int i = 0; i < arr.length - 1; i++) {
    //是否已经有序的标记,默认有序
    boolean isSorted = true;
    for (int j = 0; j < arr.length - 1 -i; j++) {
      int tmp = 0;
      //升序排序>,降序排序<
      if (arr[j] > arr[j + 1]){
        tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
        //发生元素交换,序列仍是无序状态
        isSorted = false;
      }
    }
    if (isSorted){
        break;
    }
  }
}

以isSorted作为标记。如果在本轮排序中,元素有交换,则说明数列无序;

如果没有元素交换,则说明数列已然有序,然后直接跳出大循环。

第 3 版代码

以新的无序数列 {3,4,2,1,6,7,8,9}为例,发现前半部分是无序的,而后半部分[6 ,7 ,8 ,9]是有序区间

图解冒泡排序,鸡尾酒排序

如果以上面的第2版代码执行,会发现只有前半部分的比较是有意义的,而后半部分的有序区间的比较是无意义

图解冒泡排序,鸡尾酒排序

怎么避免这种情况?那么可以在每一轮的排序后,记录下来最后一次元素交换的位置,该位置即为无序数列的边界,再往后就是有序区

public static void bubbleSort(int[] arr){
  if (arr == null || arr.length == 0return;
  //记录记录下来最后一次元素交换的位置
  int lastExchangeIndex = 0;
  //无序数列的边界,每次比较只需要比到这里为止
  int sortBorder = arr.length-1;
  for (int i = 0; i < arr.length - 1; i++) {
    //是否已经有序的标记,默认有序
    boolean isSorted = true;
    for (int j = 0; j < sortBorder; j++) {
      int tmp = 0;
      //升序排序>,降序排序<
      if (arr[j] > arr[j + 1]){
        tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
        //发生元素交换,序列仍是无序状态
        isSorted = false;
        //更新为最后一次交换元素的位置
        lastExchangeIndex = j;
      }
    }
    //更新无序数列的边界
    sortBorder = lastExchangeIndex;
    if (isSorted){
      break;
    }
  }
}

在第3版代码中,sortBorder就是无序数列的边界。在每一轮排序过程中,处于sortBorder之后的元素就不需要再进行比较了,肯定是有序的

算法升级

分析

冒泡算法的每一轮都是从左到右来比较元素,进行单向的位置交换的,是单向的

以新的无序数列 {2,3,4,5,6,7,8,1}为例,按照冒泡排序的算法,排序过程如下:

事实上,前面的[2,3,4,5,6,7,8]已经是有序了,只有元素1的位置不正确,却要进行7轮交换。

可以将算法从单向交换改为双向交换,排序过程就像钟摆一样,第1轮从左到右,第2轮从右到左,第3轮再从左到右……,这就是鸡尾酒排序.

鸡尾酒排序

图解鸡尾酒排序:

经过2轮交换(虽然实际上已经有序,但是流程并没有结束),进入第3轮交换从左到右进行。

1和2比较,位置不变;2和3比较,位置不变;3和4比较,位置不变……6和7比较,位置不变。

没有元素位置进行交换,证明已经有序,排序结束

public static void cockTailSort(int[] arr){
  if (arr == null || arr.length == 0return;
  // 记录右侧最后一次交换的位置
  int lastRightExchangeIndex = 0;
  // 记录左侧最后一次交换的位置
  int lastLeftExchangeIndex = 0;
  // 无序数列的右边界,每次比较只需要比到这里为止
  int rightSortBorder = arr.length - 1;
  // 无序数列的左边界,每次比较只需要比到这里为止
  int leftSortBorder = 0;

  //i设置为1,代表从第1轮开始
  for (int i = 1; i < arr.length; i++) {
    boolean isSorted = true;
    //奇数,从左到右
    if (i % 2 != 0) {
      for (int j = leftSortBorder; j < rightSortBorder; j++) {
        if (arr[j] > arr[j + 1]) {
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
          //发生元素交换,序列仍是无序状态
          isSorted = false;
          //更新为右侧最后一次交换元素的位置
          lastRightExchangeIndex = j;
        }
      }
    } else {
      //偶数,从右到左
      for (int j = rightSortBorder; j > leftSortBorder; j--) {
        if (arr[j] < arr[j - 1]) {
          int temp = arr[j];
          arr[j] = arr[j - 1];
          arr[j - 1] = temp;
          //发生元素交换,序列仍是无序状态
          isSorted = false;
          //更新为左侧最后一次交换元素的位置
          lastLeftExchangeIndex = j;
        }
      }
    }
    //更新无序数列的左边界
    leftSortBorder = lastLeftExchangeIndex;
    //更新无序数列的右边界
    rightSortBorder = lastRightExchangeIndex;
    if (isSorted) {
      break;
    }
  }
}

优缺点

鸡尾酒排序的优点是能够在特定条件下,减少排序的回合数

而缺点也很明显,就是代码量几乎增加了1倍。

应用场景

无序数列中大部分元素已经有序

https://juejin.im/post/6868857870423687181

回复:Java实战项目视频教程:即可获取200G,27套实战项目视频教程

回复:Java 学习路线,即可获取2020年最新最全的一份学习路线图

回复:Java 电子书,即可领取 13 本顶级程序员必读书籍

回复:Java 全套教程,即可领取:Java 基础、Java web、JavaEE 全部的教程,包括 spring boot 等

回复:简历模板,即可获取 100 份精美简历


IT老哥 发起了一个读者讨论 欢迎留言