定义

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的稳定排序算法

算法原理

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

排序过程

Bubble_sort_animation.gif

算法描述

  1. 比较相邻的元素，如果第一个比第二个大，则交换
  2. 对每一对相邻的元素作此操作，从第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数
  3. 针对所有的元素重复以上步骤，除了最后一个
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

    伪代码

    1. function bubbleSort(array, length) {
    2.  var i, j;
    3.  for (i from 0 to length - 1) {
    4.      for (j from 0 to length - 1 - i{
    5.          if (arr[j] > arr[j + 1]{
    6.              swap(arr[j], arr[j + 1])
    7.          }
    8.      }
    9.  }
    10. }
    1. 函数 冒泡排序 输入 一个数组名称为array 其长度为length 
    2.  i 从 0 到 (length - 1) 
    3.      j 从 0 到 (length - 1 - i) 
    4.          如果 array[j] > array[j + 1] 
    5.              交换 array[j] 和 array[j + 1] 的值 
    6.          如果结束 
    7.      j循环结束 
    8.  i循环结束 
    9. 函数结束

    助记码

    1. i∈[0,N-1)               //循环N-1遍
    2. j∈[0,N-1-i)           //每遍循环要处理的无序部分
    3.   swap(j,j+1)          //两两排序（升序/降序）
    image.png

    复杂度

    | 平均时间复杂度 | O(n^2) | | —- | —- | | 最坏时间复杂度 | O(n^2) | | 最优时间复杂度 | O(n) | | 空间复杂度 | 总共O(n)，需要辅助空间O(1) | | 最佳解 | No | | 排序方式 | in-place | | 稳定性 | 稳定 |

Java代码

  1.     // 基础版本
  2.     public void bubbleSort(List<Integer> list) {
  3.         int length = list.size();
  4.         for (int i = 0; i < length - 1; i++) {
  5.             for (int j = 0; j < length - 1 - i; j++) {
  6.                 if (list.get(j) > list.get(j + 1)) {
  7.                     swap(list, j, j+1);
  8.                 }
  9.             }
  10.         }
  11.     }
  13.     // 改进版本
  14.     public void bubbleSortV2(List<Integer> list) {
  15.         int length = list.size();
  16.         for (int i = 0; i < length - 1; i++) {
  17.             // 是否发生交换。没有交换，提前跳出外层循环
  18.             boolean flag = false;
  19.             for (int j = 0; j < length - 1 - i; j++) {
  20.                 if (list.get(j) > list.get(j + 1)) {
  21.                     swap(list, j, j+1);
  22.                     flag = true;
  23.                 }
  24.             }
  25.             if (!flag) {
  26.                 break;
  27.             }
  28.         }
  29.     }
  31.     void swap(List<Integer> list,Integer a,Integer b) {
  32.         int temp = list.get(a);
  33.         list.set(a, list.get(b));
  34.         list.set(b, temp);
  35.     }