Bubble Sort - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

一分钟学会写冒泡排序 冒泡排序法

图解

详解

经典排序算法（1）—— 冒泡排序算法详解 冒泡排序 ——《图解算法》 排序算法 —— 冒泡排序(一) 三分钟彻底理解冒泡排序

标准写法

步骤1: 元素交换

public static void bubbleSort(int[] arr) {
    int temp = 0;
    
    temp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = temp;
}

步骤2: 两层循环

• 外层循环：需要比较的轮数，把N个数进行N-1轮排序
• 内层循环：在当前轮中，遍历每一个元素并比较

public static void bubbleSort(int[] arr) {
    int temp = 0;

    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
	        temp = arr[j];
	        arr[j] = arr[j + 1];
	        arr[j + 1] = temp;
	    }
        }
    }
}

步骤3: 优化

public static void bubbleSort(int[] arr) {
    int temp = 0;
    // flag: 在一次循环中是否发生过数据交换。true：表示发生过交换，false：表示未发生过交换
    boolean flag = true;

    for (int i = 0; i < arr.length - 1; i++) {
        // 每一轮都能够确认一个元素（降序是从前往后，升序是从后往前）的位置
        // 因此，每进行一轮，内层循环都能减少一次遍历
        // 若没有进行过交换，证明序列已经有序，不必继续进行下去
        if (!flag) {
            break;
        }
        // 每次循环都先置为false，即认为不会发生交换
        flag = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                // 发生了交换
                flag = true;
            }
        }
    }
}

步骤4: 优化2

public static void bubbleSort(int[] arr) {
    int temp = 0;
    // flag: 在一次循环中是否发生过数据交换。true：表示发生过交换，false：表示未发生过交换
    boolean flag = true;
    // 上一次内层循环上界值，在第一次循环时与arr.length-1-i相等，即：arr.length-1。也就是说默认是最后一个
    int l = arr.length - 1;

    for (int i = 0; i < arr.length - 1; i++) {
        // 每一轮都能够确认一个元素（降序是从前往后，升序是从后往前）的位置
        // 因此，每进行一轮，内层循环都能减少一次遍历
        // 若没有进行过交换，证明序列已经有序，不必继续进行下去
        if (!flag) {
            break;
        }
        // 每次循环都先置为false，即认为不会发生交换
        flag = false;
        // 记录上一次内层循环时最后一次交换的位置
        int last = 0;
        for (int j = 0; j < l; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                // 将第一次出现该次不再交换数据时的位置下标找到，然后把这个值作为内层循环j的上限值
                // 这样内层循环就会减少一些循环
                last = j;
                // 发生了交换
                flag = true;
            }
        }
        // 让下一次循环的上界值变成此次循环的最后一次交换的位置
        l = last;
    }
}

要点

• 把N个数进行N-1轮排序，注意是"轮"
• 既可以升序排序，也可以降序排序，把if中的交换两个数的条件 arr[j] > arr[j + 1] 改为 arr[j] < arr[j + 1] 即可
• 最好时间复杂度是O(n)：已排好序；平均时间复杂度是O(n^2)；最坏时间复杂度是O(n^2)：倒序
• 空间复杂度O(1)