冒泡排序是最直覺的排序方式之一:反覆比較相鄰的兩個元素,若順序不對就交換位置,每一趟都能把當前未排序區間中最大(或最小)的元素推到末端,就像氣泡從水底浮上水面一樣,名稱也由此而來。
就效能而言,它並不划算。最差與平均時間複雜度都是 O(n²),而排序過程只需常數級的額外空間。
1. 每一趟從後往前掃描,比較相鄰元素的大小。
2. 若左邊的元素較大,就交換兩者位置。
3. 共進行 n-1 趟,每趟的比較範圍逐次收窄。
實作時值得加入一個「本趟是否發生交換」的旗標:如果某一趟完全沒有交換,代表資料已排序完成,可以直接結束迴圈,省去後續無效的比較。
+(void)bubbleSort:(NSMutableArray *)list {
if (list.count <= 1) {
return;
}
int i, y;
BOOL bFinish = YES; // 是否已發生過資料交換
// 外層控制趟數:最多 n-1 趟,一旦提前有序即可提早結束
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; // 本趟有交換,還需要下一趟
}
}
}
}
若輸入資料本身已接近有序,這個旗標能讓實際比較次數大幅下降,是冒泡排序最常見的優化手法。