冒泡排序

基本思想

每次比较两个相邻的元素，如果他们的顺序错误就交换这两个元素。

图解

给定一个数组[9, 6, 1, 5, 2, 4, 3, 8 , 7, 0]，我们进行从小到大排序。

冒泡排序的流程如下：

bubble_01@2x.png

首先第一遍，第1位是9，第2位是6。我们发现6比9小，因为我们希望越大越在后面，因此需要交换两个数的位置。则交换之后数组顺序变成:[6, 9, 1, 5, 2, 4, 3, 8 , 7, 0]。

按照以上的方法，继续比较第2位[9]和第3位[1]的，由于1比9小，因此，我们继续交换这两个数的位置。则交换之后数组顺序变成：[6, 1, 9, 5, 2, 4, 3, 8 , 7, 0]。

依次比较9次，则第一趟结束之后数组顺序变成:[6, 1, 5, 2, 4, 3, 8 , 7, 0, 9]。

则当前数组中最大的值已经放在了最后一位，冒泡排序每一趟只能确定将一个数放到相应的位置。第二趟开始，我们只需要比较最后一位前面9个数就可以了。

总结

冒泡排序：如果有n个数进行排序，只需将n-1个数归为，也就是说要进行n-1趟操作。而“每一趟”都需要将从第1位开始进行相邻的两个数比较，将较小的一位放在前面，比较完毕后向后挪一位继续比较下面两个相邻数的大小，重复以上步骤，直到最后一个尚未归为的数，归为到对应位置无序比较。

代码

- (NSArray<NSNumber *> *)bubbleSort {
    NSInteger arrayCount = self.numArray.count;
    NSMutableArray *mutArray = [NSMutableArray arrayWithArray:self.numArray];
    for (NSInteger i = 0; i < arrayCount - 1; i++) {
       for (NSInteger j = 0; j < arrayCount - 1 - i; j++) {
             if ([mutArray[j] intValue] > [mutArray[j + 1] intValue]) {
                 NSNumber *temp = mutArray[j];
                 mutArray[j] = mutArray[j + 1];
                 mutArray[j + 1] = temp;
             }
         }
         NSLog(@"第[%ld]趟:%@", (long)(i + 1), mutArray);
     }
     return [NSArray arrayWithArray:mutArray];
}

输出：

第[1]趟:(6, 1, 5, 2, 4, 3, 8, 7, 0, 9)
第[2]趟:(1, 5, 2, 4, 3, 6, 7, 0, 8, 9)
第[3]趟:(1, 2, 4, 3, 5, 6, 0, 7, 8, 9)
第[4]趟:(1, 2, 3, 4, 5, 0, 6, 7, 8, 9)
第[5]趟:(1, 2, 3, 4, 0, 5, 6, 7, 8, 9)
第[6]趟:(1, 2, 3, 0, 4, 5, 6, 7, 8, 9)
第[7]趟:(1, 2, 0, 3, 4, 5, 6, 7, 8, 9)
第[8]趟:(1, 0, 2, 3, 4, 5, 6, 7, 8, 9)
第[9]趟:(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

复杂度

由上面代码可知，每一趟排序我们需要比较n次，我们共需要n趟，所以复杂度为O(n^2)。