冒泡排序
- (NSArray *)bubbleSort:(NSArray *)array {
NSMutableArray *a = [array mutableCopy];
NSUInteger n = a.count;
for (NSUInteger i=1; i
快速排序（雙向掃描版）
- (void)quickSort:(NSMutableArray *)a left:(NSUInteger)l right:(NSUInteger)r {
if (l >= r) return;
NSInteger pivot = [a[l] integerValue];
NSUInteger i=l, j=r;
while (i < j) {
while (i= pivot) j--;
a[i] = a[j];
while (i
複雜度對比
| 算法 | 平均 | 最好 | 最壞 | 穩定性 |
|---|
| 冒泡 | O(n²) | O(n²) | O(n²) | 穩定 |
| 快速 | O(n log n) | O(n log n) | O(n²) | 不穩定 |
性能測試代碼
for (int t=1; t<=5; t++) {
NSMutableArray *arr = [NSMutableArray array];
for (int i=0; i<2000; i++) [arr addObject:@(arc4random_uniform(100000))];
// 系統排序
CFAbsoluteTime t1 = CFAbsoluteTimeGetCurrent();
NSArray *sys = [arr sortedArrayUsingSelector:@selector(compare:)];
NSLog(@"系統排序: %.0f ms", (CFAbsoluteTimeGetCurrent()-t1)*1000);
// 冒泡
CFAbsoluteTime t2 = CFAbsoluteTimeGetCurrent();
NSArray *bb = [self bubbleSort:arr];
NSLog(@"冒泡排序: %.0f ms", (CFAbsoluteTimeGetCurrent()-t2)*1000);
}
總結
- iOS 開發多用系統
sortedArrayUsingSelector:（底層快速排序）。
- 理解經典算法有助於面試與特殊場景優化。
- 快速排序平均快得多，但極端情況退化，需隨機化基準值。
