一、原理
每次比較兩個(gè)相鄰的元素枕面，將較大的元素交互到后端
二愿卒、具體流程
- 比較相鄰的兩個(gè)元素，如果第一個(gè)比第二個(gè)大就交換位置
- 對(duì)每個(gè)相鄰的元素進(jìn)行比較膊畴，從開(kāi)始第一個(gè)元素到結(jié)尾的最后一個(gè)元素掘猿，每輪循環(huán)比較之后，最后的是最大的元素
- 每一次這樣的循環(huán)之后都會(huì)有一個(gè)最大的數(shù)在后面唇跨，每確定一個(gè)最大的數(shù)稠通，那個(gè)數(shù)在最后面就不需要比較它這是內(nèi)循環(huán)
- 每次循環(huán)確定最大數(shù)移到最后，每次外循環(huán)的次數(shù)減一次（外循環(huán)）
三买猖、圖解排序過(guò)程
-
一次冒泡的圖解過(guò)程流程如下圖
第一次冒泡圖中可以看出經(jīng)過(guò)一次冒泡之后改橘，a[4] 這個(gè)個(gè)元素變成最大的數(shù)字 7，經(jīng)過(guò) N 次這樣的操作之后玉控，那么數(shù)組中所有的元素像氣泡一樣漂浮到相應(yīng)的位置
-
經(jīng)過(guò) N 次這樣操作之后的冒泡之后結(jié)果如下
冒泡結(jié)果
四飞主、代碼示例
public class BubbleSort {
public static void bubbleSort(int[] args) {
int length = args.length;
int[] bubbleSort = new int[length];
if (length <= 1) {
return;
}
for (int i = 0; i < length; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < length - 1 - i; j++) {
if (args[j] > args[j + 1]) {
int temp = args[j];
args[j] = args[j + 1];
args[j + 1] = temp;
}
}
sb.append("第-" + i + "-次：");
for (int arg : args) {
sb.append(arg + "；");
}
System.out.println(sb.toString());
}
}
public static void main(String[] args) {
int[] args1 = new int[]{7, 2, 1, 3, 2};
bubbleSort(args1);
for (int i : args1) {
System.out.print(i + ",");
}
}
}
- 運(yùn)行結(jié)果：
image-20201028203257582
-
從上面的運(yùn)行結(jié)果可以看出，經(jīng)過(guò)兩次的冒泡之后碌识，其實(shí)這個(gè)排序已經(jīng)完成碾篡，但是還是執(zhí)行了比較的操作，于是考慮代碼邏輯上是否有優(yōu)化的空間筏餐，優(yōu)化如下：
public class BubbleSort { public static void bubbleSort(int[] args) { int length = args.length; int[] bubbleSort = new int[length]; if (length <= 1) { return; } for (int i = 0; i < length; i++) { StringBuilder sb = new StringBuilder(); //優(yōu)化后 // 提前退出冒泡循環(huán)的標(biāo)志位,即一次比較中沒(méi)有交換任何元素开泽，這個(gè)數(shù)組就已經(jīng)是有序的了 boolean bubbleChange = false; for (int j = 0; j < length - 1 - i; j++) { if (args[j] > args[j + 1]) { int temp = args[j]; args[j] = args[j + 1]; args[j + 1] = temp; bubbleChange = true; } } //優(yōu)化后 if (!bubbleChange) break; sb.append("第-" + i + "-次："); for (int arg : args) { sb.append(arg + "；"); } System.out.println(sb.toString()); } } public static void main(String[] args) { int[] args1 = new int[]{7, 2, 1, 3, 2}; bubbleSort(args1); for (int i : args1) { System.out.print(i + ","); } } }運(yùn)行結(jié)果:
image-20201028203737513
五魁瞪、時(shí)間復(fù)雜度
冒泡排序總的平均時(shí)間復(fù)雜度為：O(n2)
