a[j+1],則交換兩個(gè)元素,兩兩都比較一遍稱(chēng)為一輪冒泡,結(jié)果是讓最大的元素排至最后。實(shí)現(xiàn)冒泡程序的代碼如下:" />
更新時(shí)間:2022-01-11 來(lái)源:黑馬程序員 瀏覽量:
(1)要求
能夠用自己語(yǔ)言描述冒泡排序算法
能夠手寫(xiě)冒泡排序代碼
了解一些冒泡排序的優(yōu)化手段
(2)算法描述
(3)算法實(shí)現(xiàn)
實(shí)現(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)化點(diǎn)1:每經(jīng)過(guò)一輪冒泡,內(nèi)層循環(huán)就可以減少一次
優(yōu)化點(diǎn)2:如果某一輪冒泡沒(méi)有發(fā)生交換,則表示所有數(shù)據(jù)有序,可以結(jié)束外層循環(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("比較次數(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ù),如果這個(gè)值為零,表示整個(gè)數(shù)組有序,直接退出外層循環(huán)即可。