您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發綜合

Objective-C 冒泡排序實作示範與原理解析

編輯:iOS 開發綜合

演算法原理

冒泡排序是最直覺的排序方式之一:反覆比較相鄰的兩個元素,若順序不對就交換位置,每一趟都能把當前未排序區間中最大(或最小)的元素推到末端,就像氣泡從水底浮上水面一樣,名稱也由此而來。

就效能而言,它並不划算。最差與平均時間複雜度都是 O(n²),而排序過程只需常數級的額外空間。

  • 最差時間複雜度:O(n²)
  • 平均時間複雜度:O(n²)

實作思路

1. 每一趟從後往前掃描,比較相鄰元素的大小。
2. 若左邊的元素較大,就交換兩者位置。
3. 共進行 n-1 趟,每趟的比較範圍逐次收窄。

實作時值得加入一個「本趟是否發生交換」的旗標:如果某一趟完全沒有交換,代表資料已排序完成,可以直接結束迴圈,省去後續無效的比較。

Objective-C 程式碼

+(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; // 本趟有交換,還需要下一趟
            }
        }
    }
}

若輸入資料本身已接近有序,這個旗標能讓實際比較次數大幅下降,是冒泡排序最常見的優化手法。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved