iOS 冒泡排序

  冒泡排序(BubbleSort)是刚刚接触编程的时候就开始接触的第一个排序算法

最基础实现方式

- (void)sort
{
    NSInteger count = self.sortArray.count;
    for (NSInteger end = count - 1; end >= 0; end--) {
        for (NSInteger begain = 1; begain <= end; begain++) {
            if ([self compareObjcet:self.sortArray[begain] anotherObject:self.sortArray[begain - 1]] == YES) {
                [self swapObjectWithIndex:begain anotherIndex:begain - 1];
            }
        }
    }
}

  两层for循环简单粗暴，但是很明显是可以优化的。

优化点--当队列提前变得有序时，提前结束循环

Q:那么如何确定已经提前有序了呢？
A:只需要内部循环下来一次交换都没有发生过，就说明此序列已经有序，就可以提前结束了。即在交换中有一个标识即可。

- (void)sort
{
    NSInteger count = self.sortArray.count;
    for (NSInteger end = count - 1; end >= 0; end--) {
        BOOL isSorted = YES;
        for (NSInteger begain = 1; begain <= end; begain++) {
            if ([self compareObjcet:self.sortArray[begain] anotherObject:self.sortArray[begain - 1]] == YES) {
                [self swapObjectWithIndex:begain anotherIndex:begain - 1];
                isSorted = NO;
            }
        }
        if (isSorted) {
            NSLog(@"end = %ld", end);
            break;
        }
    }
}

既然整体数列会提前有序，那么当数列部分有序时，冒泡排序还傻傻的以步长1，不断的进行循环。

优化点--当队列部分有序时，记录部分有序的位置，也就是偶尔迈大步子。

Q:那么如何确定下次迈多大步呢呢？
A:只需要记录最后一次交换的位置，那么此处下标减1即为下次迈步到的位置。

- (void)sort
{
    NSInteger count = self.sortArray.count;
    
    NSInteger sortedIndex; // 记录最后一次交换的位置，即最后一次交换后边的数据肯定是有序的了。下次可以直接把步子迈到这里
    for (NSInteger end = count - 1; end > 0; end = sortedIndex - 1) {
        sortedIndex = 1;
        for (NSInteger begain = 1; begain <= end; begain++) {
            if ([self compareObjcet:self.sortArray[begain] anotherObject:self.sortArray[begain - 1]] == YES) {
                [self swapObjectWithIndex:begain anotherIndex:begain - 1];
                sortedIndex = begain;
            }
        }
    }
}

总结：以上为冒泡排序算法相关的全部内容，其中比较与交换操作为了应对所有类型做了方法封装。