iOS算法之冒泡排序优化

排序

1. 冒泡排序

NSMutableArray *ary1 = [NSMutableArray arrayWithArray:@[@1,@3,@6,@8,@4,@5,@9]];
    
    for (int i = 0; i < [ary1 count] ; i++) {
        for (int j = 0; j < [ary1 count] - i - 1; j++) {
            if (ary1[j] > ary1[j+1]) {
                int temp = [ary1[j] intValue];
                ary1[j] = ary1[j+1];
                ary1[j+1] = @(temp);
            }
        }
    }
    NSLog(@"%@",ary1);

时间复杂度:O（n²）。

2. 有序数组的冒泡排序优化

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

 NSMutableArray *ary1 = [NSMutableArray arrayWithArray:@[@1,@3,@6,@8,@4,@5,@9]];
    
    int flag = 0;//设置一个标记来标志一趟比较是否发生交换. 如果没有发生交换，则数组已经有序
    
    for (int i = 0; i < [ary1 count] ; i++) {
        flag = 0;
        for (int j = 0; j < [ary1 count] - i - 1; j++) {
            if (ary1[j] > ary1[j+1]) {
                flag = 1;
                int temp = [ary1[j] intValue];
                ary1[j] = ary1[j+1];
                ary1[j+1] = @(temp);
            }
        }
        if (flag == 0) break;
    }
    NSLog(@"%@",ary1);

第二种优化方式是记录最后发生交换的位置，作为下一趟比较结束的位置。

 NSMutableArray *ary1 = [NSMutableArray arrayWithArray:@[@1,@3,@6,@8,@4,@5,@9]];
    
    int flag = 0 ,k = (int)[ary1 count] - 1;//用一个变量记录下最后一个发生交换的位置，后面没有发生交换的已经有序;所以可以用这个值来作为下一次比较结束的位置
    
    for (int i = 0; i < [ary1 count] ; ++i) {
        if (flag > 0) break;

        for (int j = 0; j < k ; ++j) {
            if (ary1[j] > ary1[j+1]) {
                flag = j;
                int temp = [ary1[j] intValue];
                ary1[j] = ary1[j+1];
                ary1[j+1] = @(temp);
            }
        }
    }
    
    NSMutableArray *res = [NSMutableArray arrayWithCapacity:[ary1 count]];
    flag -= 1;
    int i = 0, j = flag; //i,j 表示的下标
    
    while (i < flag  &&  j < [ary1 count]) {
        if (ary1[i] <= ary1[j]) {
            [res addObject:ary1[i++]];
        }else{
            [res addObject:ary1[j++]];
        }
    }
    
    while (i < flag) {
        [res addObject:ary1[i++]];
    }
    
    while (j < [ary1 count]) {
        [res addObject:ary1[j++]];
    }
    
    
    NSLog(@"%@",res);

3. 两个有序数组结合成一个有序数组

    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]) {
        if (ary1[i] <= ary2[j]) {
            [res addObject:ary1[i++]];
        }else{
            [res addObject:ary2[j++]];
        }
    }
    
    while (i < [ary1 count]) {
        [res addObject:ary1[i++]];
    }
    
    while (j < [ary2 count]) {
        [res addObject:ary2[j++]];
    }
    
    NSLog(@"%@",res);

时间复杂度:O(n)