- **介紹 **
冒泡排序法又稱為交換排序逻翁，其比較方式由第一個元素開始，比較相鄰元素大小捡鱼，若大小順序有誤八回，則對調(diào)后再進(jìn)行下一個元素的比較。如此掃描過一次后就可確保最后一個元素是位于正確的順序驾诈。接著再進(jìn)行第二次掃描缠诅，直到完成所有元素的排序關(guān)系為之。 -
演示
代碼如下：
private static void bubbleSort() {
int data[] = {9, 6, 3, 2, 4, 5, 1, 8, 7};
int i, j, tmp;
for (i = data.length - 1; i > 0; i--) {
for (j = 0; j < i; j++) {
if (data[j] > data[j + 1]) {
tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
}
}
}
}
打印結(jié)果：
冒泡排序打印信息.png
-
分析
- 最壞情況及平均情況均需比較n(n-1)/2次乍迄；時間復(fù)雜度為O(n2)管引，最好情況只需要完成一次掃描，發(fā)現(xiàn)沒有做交換的操作則表示排序已經(jīng)完成闯两，所以只做了n-1次比較褥伴，是復(fù)雜度為O(n)。
- 由于冒泡排序為相鄰兩者相互比較對調(diào)漾狼，并不會更變其原本排序的順序重慢，所以是穩(wěn)定排序法。
- 只需一個額外的空間逊躁，所以空間復(fù)雜度為最佳似踱。
- 冒泡排序法適用于數(shù)據(jù)量小或者有部分?jǐn)?shù)據(jù)已經(jīng)排序過的情況。
-
優(yōu)化
通過上邊的演示可以看出冒泡排序法有一個缺點稽煤，就是不管數(shù)據(jù)是否已經(jīng)排序完成都會固定執(zhí)行n(n-1)/2次核芽，所以需要在排序中增加標(biāo)記來提前中斷程序，以此提高執(zhí)行效率念脯，代碼如下：
private static void bubbleSort() {
int data[] = {9, 6, 3, 2, 4, 5, 1, 8, 7};
int i, j, tmp, flag;
for (i = data.length - 1; i > 0; i--) {
flag = 0; // flag 用來判斷是否有執(zhí)行
for (j = 0; j < i; j++) {
if (data[j] > data[j + 1]) {
tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
flag++; // 如果有執(zhí)行過交換狞洋，則flag不為0
}
}
if (flag == 0){
break; // 如果沒有發(fā)生過交換就退出
}
}
}
-
后記
通過比較會發(fā)現(xiàn)一個有意思的現(xiàn)象，冒泡排序每次掃描都會確定后邊的元素為目標(biāo)順序绿店，而選擇排序每次都掃描都會確定前邊的元素為目標(biāo)順序庐橙。
