基础的简单算法之冒泡

一、冒泡排序回顾

1. 从头开始、比较每一个相邻元素，如果第一个比第二个大、交换
2. 一轮结束、末尾的最大
3. 忽略1中找到的最大元素,重复执行1步骤、直到所有元素有序
4. 优化：记录已经尾部局部已经有序，记录其位置，减少比较次数，提高效率

// 1. 原始版
- (NSArray *)sortByArray:(NSArray *)pendingArray {
    NSMutableArray *array = [NSMutableArray arrayWithArray:pendingArray];
    for (int i = 0; i < array.count; i++) {
        for (int j = 1; j < array.count; j++) {
            if ([array[j] intValue] < [array[j - 1]  intValue]) {
                [self swapElement:array index:j];
            }
        }
    }
    return [super sortByArray:array];
}

// 2. 改进版
- (NSArray *)sortModifiedByArray:(NSArray *)pendingArray {
    
    NSMutableArray *array = [NSMutableArray arrayWithArray:pendingArray];
    for (NSUInteger end = array.count; end > 0; end--) {
        NSUInteger sortedIndex = 1;
        for (NSUInteger begin = 1; begin < end; begin++) {
            if ([self compareValues:array index:begin]) {
                [self swapElement:array index:begin];
                sortedIndex = begin; // 记录要比较的起始位置，这里不能放到外面
            }
        }
        // 这里是将排好序的下标赋值给要遍历的最后一个值
        end = sortedIndex;
    }
    return [super sortModifiedByArray:array];
}

- (BOOL)compareValues:(NSArray *)array index:(NSUInteger)index {
    return [array[index] intValue] < [array[index - 1]  intValue];
}

- (void)swapElement:(NSMutableArray *)array index:(NSUInteger)index {
    id temp = array[index];
    array[index] = array[index - 1];
    array[index - 1] = temp;
}