一、什么是冒泡排序
1.1、文字描述
冒泡排序是一種簡單的排序算法。它重復(fù)地走訪要排序的數(shù)列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,這也就說明排序已經(jīng)完成。因為越大的元素會經(jīng)由交換慢慢‘浮‘到數(shù)列的頂端,所以命名為冒泡算法排序。
1.2、程序描述
定義一個變量 i = 0,最大值為數(shù)列的長度 - 1 , i 與 i + 1 進(jìn)行比較,如果 i > i + 1 則進(jìn)行交換。隨著 i 的不斷增加,直到 i 達(dá)到數(shù)列長度 - 1。
附動態(tài)圖:
二、簡單的代碼展示
我們先進(jìn)行最基礎(chǔ)的操作,再依次進(jìn)行比對。
PS: 這樣會產(chǎn)生一些無效的操作,后面我們再進(jìn)行優(yōu)化...
public static void main(String[] args) {
int handleTimes = 0;
/* 定義一個簡單的亂序數(shù)組 */
int[] intArr = {2,4,1,5,6,3,7};
for (int i = 0;i < intArr.length; i++) {
/* 開啟雙重循環(huán) */
for (int j = 0; j < intArr.length - i - 1; j++) {
/* 拿到當(dāng)前操作的數(shù)據(jù)和下一個進(jìn)行比較 */
if (intArr[j] > intArr[j + 1]) {
/* 我們按照從小到大排序,如果當(dāng)前的大于下一個數(shù)據(jù)則兩個數(shù)據(jù)互換 */
int temp = intArr[j];
intArr[j] = intArr[j+1];
intArr[j+1] = temp;
}
}
System.out.println("第" + handleTimes + "次排序" + CollectionUtils.arrayToList(intArr));
handleTimes++;
}
System.out.println(handleTimes);
System.out.println(CollectionUtils.arrayToList(intArr));
}
輸出如下:
三、代碼優(yōu)化
通過上面的代碼我們可以看到一共進(jìn)行了7次排序,但是從第四次開始已經(jīng)是完成了的,后面的都是無效操作。所以我們對代碼進(jìn)行了如下優(yōu)化:
① 定義一個排序生效字段 isChanged,當(dāng)排序進(jìn)行時我們使其修改為true
② 每次大循環(huán)時我們都初始isChengerd為false,當(dāng)每次大循環(huán)結(jié)束時,如果isChanged還是false,則進(jìn)行已經(jīng)沒有進(jìn)行排序了
public static void main(String[] args) {
int handleTimes = 0;
boolean isChangerd = false;
/* 定義一個簡單的亂序數(shù)組 */
int[] intArr = {2,4,1,5,6,3,7};
for (int i = 0;i < intArr.length; i++) {
isChangerd = false;
/* 開啟雙重循環(huán) */
for (int j = 0; j < intArr.length - i - 1; j++) {
/* 拿到當(dāng)前操作的數(shù)據(jù)和下一個進(jìn)行比較 */
if (intArr[j] > intArr[j + 1]) {
/* 我們按照從小到大排序,如果當(dāng)前的大于下一個數(shù)據(jù)則兩個數(shù)據(jù)互換 */
int temp = intArr[j];
intArr[j] = intArr[j+1];
intArr[j+1] = temp;
/* 這里定義一個中間變量進(jìn)行操作 */
isChangerd = true;
}
}
System.out.println("第" + handleTimes + "次排序" + CollectionUtils.arrayToList(intArr));
/* 如果這里如果上面的操作沒有交換則說明排序已經(jīng)完成 */
if (!isChangerd) {
break;
}
handleTimes++;
}
System.out.println(CollectionUtils.arrayToList(intArr));
}
輸出如下: