1. 简介

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

讲实话在我的程序员生涯中, 我从来就没有见到过哪用冒泡排序的

作为Java程序员使用最多的就是JDK的排序Collections.sort()和Arrays.sort()

但是JDK实现的排序算法主要是插入和快排以及归并, 并不是冒泡

为什么JDK不实现冒泡排序

JDK关注的是的是执行效率以及兼容性,

所以JDK的排序算法为了效率和兼容性写得有点晦涩难懂

为什么要学习冒泡排序

因为冒泡排序足够简单, 冒泡排序作为一个排序算法, 它的实现思路非常契合人类的思维

它能让一个刚学习编程的人深刻得体会到一个 时间复杂度的算法长什么样子

2. 实现

伪代码

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

代码写了两层循环

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

Java代码实现

用Java代码来实现

public static void bubbleSort(int[] arr) {
    for (int i = arr.length - 1; 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;
            }
        }
    }
}

看看效果

指令共执行了多少条?

大约是 条, 所以时间复杂度是