冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

算法分析
冒泡排序算法是所有排序算法中最简单的（前面也提到过），在生活中应该也会看到气泡从水里面出来时，越到水面上气泡就会变的越大。在物理上学气压的时候好像也看到过这种现象；其实理解冒泡排序就可以根据这种现象来理解：每一次遍历，都把大的往后面排（当然也可以把小的往后面排），所以每一次都可以把无序中最大的（最小）的元素放到无序的最后面（或者说有序元素的最开始）；

基本步骤：
1、外循环是遍历每个元素，每次都放置好一个元素；　
2、内循环是比较相邻的两个元素，把大的元素交换到后面；
3、等到第一步中循环好了以后也就说明全部元素排序好了；

//冒泡排序
- (void)bubbleSortArray:(NSMutableArray *)array {
    for (int i = 0; i < array.count-1; i++) {
        for (int j = 0; j < array.count-1-i; j++) {
            NSInteger left = [array[j] integerValue];
            NSInteger right = [array[j+1] integerValue];
            if (left > right) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
        NSLog(@"%@",array);
    }
}

时间复杂度分析

针对性能优化后的排序算法来说
最好的情况是本身就是有序的，只需要进行n-1次比较，没有数据交换，时间复杂度为O(1)
最坏的情况是表元素逆序，需要比较 (n-1) + (n-2) + … + 3 + 2 + 1 = n*(n-1)/2次比较，并作等量级的记录移动，所以总的时间复杂度为O(n^2)
总数，冒泡排序平均时间复杂度为O(n^2)

空间复杂度分析

这里的空间复杂度就是指在交换元素是那个临时变量所占的内存空间
最优空间复杂度就是开始元素顺序有序，无交换，无需使用中间变量，则空间复杂度为0最差空间复杂度就是元素逆序，则空间复杂度为O(n)，表示每次交换时中间变量都重新分配内存空间，也可以直接将中间变量定义在for循环外，为O(1)。平均空间复杂度为O(1)