OC算法01：冒泡排序探索

冒泡排序

1. 基本思路：

重复地走访要排序的元素列，依次比较两个相邻的元素，如果他们的 顺序错误就把他们交换过来。

2. 算法思想：

1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3）针对所有的元素重复以上的步骤，除了最后一个。
4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

3. 主要流程：

首先我们需要 双层循环，外层循环控制排序趟数，内存循环控制每趟比较次数以及是否需要交换位置，我们先不关心是否交换位置，我们内层循环每次比较都是取 array[j] 和 array[j+1] 相比较，根据比较结果来判断是否交换位置。

4. 时间复杂度

• 最好的情况：冒泡排序中最好的情况是数组本身就是正序排列的，并不需要交换，例如：@[1,2,3,4,5]; 当正序数组放入冒泡排序中的时候，只会进行4次比较，分别是1和2，2和3，3和4，4和5。比较完后发现没有任何数需要交换，那么说明数组已经排序正确，不要在进行最外层循环。当正序数组中有 N 个数的时候，那么只需要 N-1 次比较。 而正序数组在冒泡排序中的时间复杂度为O(n)，因为n-1中，在n的基数很大的情况，比如n为1000时，1其实可以忽略不计。所以 冒泡排序中最短的时间 **复杂度为O(n)**。

• 冒泡排序中最坏的情况是数组本身就是逆序排列的，需要每两个数都进行交换，例如：@[5,4,3,2,1]；当逆序数组放入冒泡排序中，最外层的每一次循环都要进行n-1次比较，而逆序数组需要进行n次最外层循环才能正确排序，最终比较次数为(n-1)n/2，所以冒泡排序中最长的时间 **复杂度为(n²)**，因为当n基数很大时，(n-1)n/2 = (n² - n)/2； n²与n、1/2的差距越大，n与1/2可以忽略不计。

冒泡排序

例子：元数据：@[@”1”,@”3”,@”2”,@”5”,@”4”]

NSMutableArray * arr = [NSMutableArray arrayWithArray:@[@"1",@"3",@"2",@"5",@"4"]];
    // 外循环控制排序趟数,进行 array.count-1 趟
    for (int i = 0; i < arr.count; i ++) {
        // 记录是否进行了交换，如果没有交换，数组顺序为顺序，则直接跳出外层循环结束排序
        for (int j = 0; j < arr.count - i - 1; j++) {
            // 相邻元素比较，若逆序则交换
            if ([arr[j] intValue] > [arr[j + 1] intValue]) {
                [arr exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
            }
        }
    }

打印结果：

2020-08-10 20:29:10.492517+0800 OC冒泡排序[27771:1528609] (
    1,
    2,
    3,
    4,
    5
)

有序数组冒泡排序的优化

如果数据是有序的：

• 第一种优化方式是设置一个标记位来标记是否发生了交换，如果没有发生交换就提前结束；

NSMutableArray * arr = [NSMutableArray arrayWithArray:@[@"5",@"4",@"3",@"2",@"1"]];
    int flag = 0;
    // 外循环控制排序趟数,进行 array.count-1 趟
    for (int i = 0; i < arr.count; i ++) {
        // 记录是否进行了交换，如果没有交换，数组顺序为顺序，则直接跳出外层循环结束排序
        for (int j = 0; j < arr.count - i - 1; j++) {
            //相邻元素比较，若逆序则交换
            if ([arr[j] intValue] > [arr[j + 1] intValue]) {
                flag = 1;
                id temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        if (flag == 0) {
            break;
        }
    }
    NSLog(@"%@",arr);

打印结果

2020-08-10 20:45:33.770139+0800 OC冒泡排序[28047:1546936] (
    1,
    2,
    3,
    4,
    5
)

两个数组合并成一个数据，并排序

NSArray * ary1 = @[@1,@3,@4,@5,@9];
NSArray * ary2 = @[@2,@4,@6,@8];
NSMutableArray * res = [NSMutableArray arrayWithCapacity:[ary1 count] + [ary2 count]];
    
    int i = 0, j = 0; // i 表示ary1的下标  j表示ary2的下标
    
    while (i < ary1.count  &&  j < ary2.count) {
        int a1 = [ary1[i] intValue];
        int a2 = [ary2[j] intValue];
        if (a1 <= a2) {
            [res addObject:ary1[i++]];
        }else {
            [res addObject:ary2[j++]];
        }
    }
    
    NSLog(@"%@",res);

打印

2020-08-10 21:11:11.311203+0800 OC冒泡排序[28372:1568516] (
    1,
    2,
    3,
    4,
    4,
    5,
    6,
    8
)