說說什么是冒泡排序？手撕代碼【java面試題】

（1）要求

能夠用自己語言描述冒泡排序算法

能夠手寫冒泡排序代碼

了解一些冒泡排序的優(yōu)化手段

（2）算法描述

• 依次比較數(shù)組中相鄰兩個元素大小，若 a[j] > a[j+1]，則交換兩個元素，兩兩都比較一遍稱為一輪冒泡，結(jié)果是讓最大的元素排至最后
•  重復(fù)以上步驟，直到整個數(shù)組有序

（3）算法實現(xiàn)
實現(xiàn)冒泡程序的代碼如下：

public static void bubble(int[] a) {
    for (int j = 0; j < a.length - 1; j++) {
        // 一輪冒泡
        boolean swapped = false; // 是否發(fā)生了交換
        for (int i = 0; i < a.length - 1 - j; i++) {
            System.out.println("比較次數(shù)" + i);
            if (a[i] > a[i + 1]) {
                Utils.swap(a, i, i + 1);
                swapped = true;
            }
        }
        System.out.println("第" + j + "輪冒泡"
                           + Arrays.toString(a));
        if (!swapped) {
            break;
        }
    }
}

優(yōu)化點1：每經(jīng)過一輪冒泡，內(nèi)層循環(huán)就可以減少一次

優(yōu)化點2：如果某一輪冒泡沒有發(fā)生交換，則表示所有數(shù)據(jù)有序，可以結(jié)束外層循環(huán)

（4）進一步優(yōu)化

public static void bubble_v2(int[] a) {
    int n = a.length - 1;
    while (true) {
        int last = 0; // 表示最后一次交換索引位置
        for (int i = 0; i < n; i++) {
            System.out.println("比較次數(shù)" + i);
            if (a[i] > a[i + 1]) {
                Utils.swap(a, i, i + 1);
                last = i;
            }
        }
        n = last;
        System.out.println("第輪冒泡"
                           + Arrays.toString(a));
        if (n == 0) {
            break;
        }
    }
}

每輪冒泡時，最后一次交換索引可以作為下一輪冒泡的比較次數(shù)，如果這個值為零，表示整個數(shù)組有序，直接退出外層循環(huán)即可。