Objective-C 实现排序算法

当数据量很大的时候, 可以清晰的看出 快速排序的优势。

// 冒泡排序 优化
// 正常是 for 循环 从后一直冒泡, 优化是, 如果当某次循环, 所有位置没有发生改动, 那么证明排序已经完成, 直接 break。

- (NSArray *)bubbleBetter:(NSMutableArray *)a {
    if (a.count <= 1) return [a copy];
    BOOL flag = true;
    for (int i = 0; i < a.count - 1; i++) {
        if (!flag) {
            return [a copy];
        }
        flag = false;
        for (NSInteger j = 1; j < a.count - i; j++) {
            if ([a[j - 1] integerValue] > [a[j] integerValue]) {
                [a exchangeObjectAtIndex:j - 1 withObjectAtIndex:j];
                flag = true;
            }
        }
    }
    return [a copy];
}


// 选择排序 优化
// 每次循环，找出最大的和最小的，放两边，继续查找剩余的部分。
- (NSArray *)selector:(NSMutableArray *)a {
    if (a.count <= 1) return [a copy];
    NSInteger count = a.count;
    for (int i = 0; i < a.count / 2; i++) {
        NSInteger min = i;
        NSInteger max = i;
        for (int j = i + 1; j < count - i; j++) {
            if ([a[j] integerValue] < [a[min] integerValue]) {
                min = j;
            } else if ([a[j] integerValue] > [a[max] integerValue]) {
                max = j;
            }
        }
        [a exchangeObjectAtIndex:i withObjectAtIndex:min];
        [a exchangeObjectAtIndex:count - i - 1 withObjectAtIndex:max];
    }
    return [a copy];
}

// 快速排序 
// 是从某个数开始，左边是全部小于这个数的集合， 右边是全部大于这个数的集合，通过不断递归将所有数据排完。
- (NSArray *)quick:(NSMutableArray *)a min:(NSInteger)min max:(NSInteger)max {
    if (a.count <= 1) return [a copy];
    if (max - min <= 0) return [a copy];
    NSInteger centerIndex = (max - min) / 2 + min;
    NSInteger center = [a[centerIndex] integerValue];
    NSInteger moveTimes = 0;
    for (NSInteger i = min; i < max; i++) {
        if (i == centerIndex) {
            i += moveTimes;
            continue;
        }
        if (i < centerIndex) {
            if ([a[i] integerValue] > center) {
                id temp = a[i];
                [a insertObject:temp atIndex:centerIndex + 1];
                [a removeObjectAtIndex:i];
                centerIndex--;
                i--;
                moveTimes++;
            }
        } else {
            if ([a[i] integerValue] < center) {
                id temp = a[i];
                [a insertObject:temp atIndex:centerIndex];
                [a removeObjectAtIndex:i + 1];
                centerIndex++;
            }
        }
    }
    [self quick:a min:min max:centerIndex];
    [self quick:a min:centerIndex + 1 max:max];
    return [a copy];
}