冒泡排序

冒泡排序分多個階段將陣列排序。如果元素不按順序排列，則每次傳遞都會連續交換相鄰元素。冒泡排序演算法對數組進行多次遍歷。在每次傳遞中，都會比較連續的相鄰對。如果一對按降序排列，則交換其值；否則，值保持不變。此技術稱為冒泡排序或下沉排序，因為較小的值逐漸「冒泡」到頂部，而較大的值則沉入底部。第一次遍歷後，最後一個元素成為陣列中最大的元素。第二遍之後，倒數第二個元素成為陣列中第二大的元素。這個過程一直持續到所有元素都排序完畢。

下圖 (a) 顯示了對六個元素 (2 9 5 4 8 1) 的陣列進行冒泡排序的第一遍。比較第一對中的元素（2 和 9），不需要交換，因為它們已經按順序排列。比較第二對（9 和 5）中的元素，並將 9 與 5 交換，因為 9 大於 5。比較第三對（9 和 4）中的元素，並將 9 與 4 交換。比較第四對中的元素對（9 和 8），並將 9 與 8 交換。比較第五對（9 和 1）中的元素，並將 9 與 1 交換。正在比較的對突出顯示，已排序的數字在下圖中以斜體顯示。

第一遍將最大的數字 (9) 作為數組的最後一個。在第二遍中，如下圖 (b) 所示，您按順序對元素對進行比較和排序。不需要考慮最後一對，因為數組中的最後一個元素已經是最大的了。在第三遍中，如下圖 (c) 所示，您將按順序對除最後兩個元素之外的元素對進行比較和排序，因為它們已經按順序排列。所以在第 k 遍中，你不需要考慮最後 k - 1 個元素，因為它們已經排序了。

冒泡排序的演算法在下面的程式碼中描述。

for (int k = 1; k // 執行第 k 遍
for (int i = 0; i if (列表[i] > 列表[i + 1])
將 list[i] 與 list[i + 1] 交換；
}
}

請注意，如果一次傳遞中沒有發生交換，則無需執行下一次傳遞，因為所有元素都已排序。您可以使用此屬性來改進上面程式碼中的演算法，如下程式碼所示。

布林 needNextPass = true;
for (int k = 1; k // 陣列可能已排序且不需要下次遍歷
needNextPass = false;
// 執行第 k 遍
for (int i = 0; i if (列表[i] > 列表[i + 1]) {
將 list[i] 與 list[i + 1] 交換；
需要下一個通行證 = true; // 還需要下次傳遞
}
}
}

演算法可以用下面的程式碼實作

在最好的情況下，冒泡排序演算法只需要第一遍就可以發現陣列已經排序，不需要下一步。由於第一遍的比較次數為 n - 1，因此冒泡排序的最佳情況時間為 O(n)。

在最壞的情況下，冒泡排序演算法需要 n - 1 次。第一遍進行 n - 1 次比較；第二遍進行 n - 2 次比較；等等;最後一遍進行 1 次比較。因此，比較的總數為：

因此，冒泡排序最壞情況的時間是 O(n^2)。

以上是冒泡排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！