您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 教學 >> iOS 相關教學

Objective-C 冒泡排序實作與提前結束優化示例

編輯:iOS 相關教學

演算法原理

冒泡排序是最直覺的排序方式:反覆比較相鄰的兩個元素,若順序不對就交換,每一輪都能把當前未排序區間中最大(或最小)的元素送到它最終該在的位置,就像氣泡從水底浮上水面。

需要進行 n-1 趟比較,第 j 趟只需比較 n-j 次(j 為已排定的元素個數)。它的空間複雜度是 O(1)(在原陣列上反覆交換,只需常數級暫存),但時間效率不佳:

1. 最差時間複雜度:O(n²)
2. 平均時間複雜度:O(n²)

實作思路

1. 每一趟都比較相鄰兩元素;
2. 若左邊比右邊大,就交換;
3. 重複 n-1 趟。

Objective-C 代碼

下面的版本加了一個小優化:用 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²) 的迴圈。

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