1. 简介

冒泡排序是我记事以来学的第一个排序算法

讲实话在我的程序员生涯中, 生产中我从来就没有见到过冒泡排序
作为Java程序员使用最多的就是JDK的排序Collections.sort()和Arrays.sort()但是JDK实现的排序算法主要是插入和快排以及归并

1.1 为什么JDK不实现冒泡排序呢?

JDK关注的是生产中的运用, 生产环境关注的是执行效率以及兼容性, 所以JDK的排序算法写得有点晦涩难懂

1.2 那为什么我们还要了解冒泡排序呢?

因为冒泡排序足够简单, 冒泡排序作为一个排序算法,
它的实现思路非常契合人类的思维, 它能让一个刚学习编程的人深刻得体会到一个冒泡排序O(n²) - 图1时间复杂度的算法长什么样子

2. 实现

2.1 伪代码

  1. BUBBLE_SORT(A)
  2.   for i = A.length to 0
  3.     for j = 0 to i
  4.       if A[j] > A[j+1]
  5.         swap(A[j], A[j+1])

代码写了两层循环
主要逻辑在内层循环, 内层循环总是将此次遍历最大的数移到 最后面 i 的位置

2.2 Java代码

用Java代码来实现

  1. public static void bubbleSort(int[] arr) {
  2.     for (int i = arr.length - 1; i > 0; i--) {
  3.         for (int j = 0; j < i; j++) {
  4.             if (arr[j] > arr[j + 1]) {
  5.                 int temp = arr[j];
  6.                 arr[j] = arr[j+1];
  7.                 arr[j+1] = temp;
  8.             }
  9.         }
  10.     }
  11. }

看看效果

指令共执行了多少条?
大约是 冒泡排序O(n²) - 图2条, 所以时间复杂度自然是 冒泡排序O(n²) - 图3