Objective-C 實現冒泡排序與快速排序：從原理到工程化封裝

Objective-C 實現冒泡排序與快速排序：從原理到工程化封裝

排序算法是面試與工程基礎。本文以 Objective-C 為語言，封裝 Sort 類實現冒泡排序與快速排序，詳細註解分區邏輯、遞歸終止條件、邊界處理，並分析時間複雜度與穩定性差異。

類介面設計

// Sort.h
#import 

@interface Sort : NSObject

@property (nonatomic, strong) NSMutableArray* dataSource;

- (void)bubbleSort:(NSMutableArray*)dataSource;
- (void)quickSort:(NSInteger)start endIndex:(NSInteger)end;

@end

冒泡排序實現——穩定、簡單、O(n²)

// Sort.m - 冒泡排序
- (void)bubbleSort:(NSMutableArray*)dataSource {
    NSUInteger count = dataSource.count;
    for (NSUInteger i = 0; i < count; ++i) {
        for (NSUInteger j = 0; j < count - i - 1; ++j) {
            if ([dataSource[j] integerValue] > [dataSource[j+1] integerValue]) {
                [dataSource exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
    // 列印驗證
    for (NSUInteger i = 0; i < dataSource.count; ++i) {
        NSLog(@"排序--%@", dataSource[i]);
    }
}

特性：穩定排序、原地排序、最佳 O(n)（已有序）、最壞/平均 O(n²)、適合小規模/近乎有序數據。

快速排序實現——分治法、不穩定、平均 O(n log n)

// Sort.m - 快速排序
- (void)quickSort:(NSInteger)start endIndex:(NSInteger)end {
    if (start >= end) return;  // 遞歸終止：區間長度 ≤ 1
    
    NSInteger pivot = [_dataSource[start] integerValue];
    NSInteger left = start, right = end;
    NSInteger i = start, j = end;
    
    while (i < j) {
        // 從右向左找 < pivot
        while (i < j && [_dataSource[j] integerValue] >= pivot) --j;
        if (i < j) _dataSource[i++] = _dataSource[j];
        
        // 從左向右找 > pivot
        while (i < j && [_dataSource[i] integerValue] <= pivot) ++i;
        if (i < j) _dataSource[j--] = _dataSource[i];
    }
    
    _dataSource[i] = @(pivot);  // 基準值歸位
    
    [self quickSort:left endIndex:i-1];   // 處理左分區
    [self quickSort:i+1 endIndex:right];  // 處理右分區
}

分區邏輯圖解（以 [15,32,8,99,12,17,36] 為例）

1. 基準值 = 15（索引 0）
2. 右→左掃描：36≥15, 17≥15, 12<15 → 停在索引 4，將 12 移到索引 0
3. 左→右掃描：32>15 → 停在索引 1，將 32 移到索引 4
4. 繼續雙向掃描直到 i==j，將基準值 15 放入最終位置
5. 遞歸處理左右子陣列

複雜度與穩定性對比

主程式調用範例

NSMutableArray* data = [@[@10, @88, @97, @33, @8, @73, @18] mutableCopy];

Sort* sorter = [[Sort alloc] init];

NSLog(@"=== 冒泡排序 ===");
[sorter bubbleSort:data];

sorter.dataSource = data;  // 快排使用實例屬性
NSLog(@"=== 快速排序 ===");
[sorter quickSort:0 endIndex:data.count-1];

for (id obj in data) NSLog(@"最終: %@", obj);

工程化優化建議

• 三數取中：取首、中、末三者中位數作基準，避免有序序列退化
• 小區間切換插入排序：長度 < 10 時改用插入排序，減少遞歸開銷
• 尾遞歸優化：對較大分區遞歸，較小分區迭代，限制棧深度
• 泛型化：接受 NSComparator 區塊或 SEL，支援任意對象排序
• 非遞歸版：用顯式棧模擬遞歸，完全避免棧溢位風險

常見錯誤避坑

1. 遞歸終止條件寫成 start > end 導致單元素區間仍遞歸
2. 分區迴圈條件 i <= j 導致越界或死循環
3. 基準值歸位時未轉回 NSNumber（陣列存對象）
4. 未處理重複元素導致分區極度不平衡（可用三向切分優化）

通過封裝 Sort 類，我們將經典算法轉化為可復用、可測試、可擴展的組件，這正是從「寫出算法」到「工程化算法」的關鍵一步。