教育行業(yè)A股IPO第一股(股票代碼 003032)

全國咨詢(xún)/投訴熱線(xiàn):400-618-4000

什么是冒泡排序?手寫(xiě)一段冒泡排序的代碼

更新時(shí)間:2022年01月10日16時(shí)47分 來(lái)源:黑馬程序員 瀏覽次數:

(1)要求

能夠用自己語(yǔ)言描述冒泡排序算法

能夠手寫(xiě)冒泡排序代碼

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

(2)算法描述

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

(3)算法實(shí)現
實(shí)現冒泡程序的代碼如下:

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("比較次數" + 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)化點(diǎn)1:每經(jīng)過(guò)一輪冒泡,內層循環(huán)就可以減少一次

優(yōu)化點(diǎn)2:如果某一輪冒泡沒(méi)有發(fā)生交換,則表示所有數據有序,可以結束外層循環(huán)

(4)進(jìn)一步優(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("比較次數" + 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í),最后一次交換索引可以作為下一輪冒泡的比較次數,如果這個(gè)值為零,表示整個(gè)數組有序,直接退出外層循環(huán)即可。

猜你喜歡:

Java算法之冒泡排序【超詳細】

Java如何實(shí)現冒泡排序算法?

JavaEE就業(yè)筆記串講---Maven-part2

delete()方法刪除文件及目錄

黑馬程序員java高級軟件工程師就業(yè)班課程

0 分享到:
和我們在線(xiàn)交談!