冒泡排序是最直覺的排序方式:反覆比較相鄰的兩個元素,若順序不對就交換,每一輪都能把當前未排序區間中最大(或最小)的元素送到它最終該在的位置,就像氣泡從水底浮上水面。
需要進行 n-1 趟比較,第 j 趟只需比較 n-j 次(j 為已排定的元素個數)。它的空間複雜度是 O(1)(在原陣列上反覆交換,只需常數級暫存),但時間效率不佳:
1. 最差時間複雜度:O(n²)
2. 平均時間複雜度:O(n²)
1. 每一趟都比較相鄰兩元素;
2. 若左邊比右邊大,就交換;
3. 重複 n-1 趟。
下面的版本加了一個小優化:用 bFinish 標記本趟是否發生過交換,若某趟完全沒有交換,說明資料已有序,直接跳出迴圈。這對「接近有序」的輸入能省下大量無效比較。
+(void)bubbleSort:(NSMutableArray *)list{
if (list.count <= 1) {
return;
}
int i, y;
BOOL bFinish = YES; // 是否發生過數據交換
for (i = 1; i <= [list count] && bFinish; i++) {
bFinish = NO; // 每趟開始前重置標記
// 從末尾往前掃,與前一位比較,較小則交換
for (y = (int)[list count] - 1; y >= i; y--) {
if ([[list objectAtIndex:y] intValue] < [[list objectAtIndex:y-1] intValue]) {
[list exchangeObjectAtIndex:y-1 withObjectAtIndex:y];
bFinish = YES; // 本趟有交換,繼續下一趟
}
}
}
}
這裡用 exchangeObjectAtIndex:withObjectAtIndex: 交換元素,比手動取出、覆寫、再放回簡潔,也不容易出錯。
需要注意的是,示例直接對元素取 intValue,意味著它只適用於數字集合。若要推廣到任意可比較對象,應改用 compare: 方法:
if ([objB compare:objA] == NSOrderedAscending) {
[list exchangeObjectAtIndex:y-1 withObjectAtIndex:y];
}
最後談談實用性。冒泡排序的價值主要在教學——它讓人理解「比較與交換」這個最基本的排序動作。真實專案裡,若資料量小直接用 sortedArrayUsingComparator: 就好;資料量大時也應該交給系統的排序實現,而不必自己寫 O(n²) 的迴圈。