iOS之你写出了一个真正的冒泡排序吗？

冒泡排序的定义如下：
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”

比如我们有一个数组

NSArray *array = @[@4, @14, @1, @38, @26, @9, @101, @7];

那么我们按照冒泡排序的定义交换应该如下：

第一轮循环	交换结果
第一次	4，1，14，38，26，9，101，7
第二次	4，1，14，26，38，9，101，7
第三次	4，1，14，26，9，38，101，7
第四次	4，1，14，26，9，38，101，7
第五次	4，1，14，26，9，38，7，101

至此第一轮交换结束，次轮交换结果已经将最大的值交换到末尾。
那么我们开始第二轮循环

第二轮循环	交换结果
第一次	1，4，14，26，9，38，7，101
第二次	1，4，14，9，26，38，7，101
第三次	1，4，14，9，26，7，38，101

至此第二轮循环完成，接下来依次类推最终我们排序后的数组内容应该是：

[1,4,7,9,14,26,38,101];

理论部分演示完毕。
接下来就是代码部分：
头脑里面还有了思路之后，我上来就写了以下代码：

-(NSArray*)bubbleSort:(NSArray*)array
{
    NSInteger execCount = 0;
    NSMutableArray *sortArray = [NSMutableArray arrayWithArray:array];
    for (NSInteger i = 0; i < sortArray.count; i++)
    {
        for (NSInteger j = i + 1; j < sortArray.count; j++)
        {
            if ([sortArray[i] integerValue] > [sortArray[j] integerValue])
            {
                [sortArray exchangeObjectAtIndex:i withObjectAtIndex:j];
                [self displayArray:sortArray];
                execCount++;
            }
        }
    }
    NSLog(@"共执行了%ld次", execCount);
    return sortArray;
}
-(void)displayArray:(NSArray*)array
{
    NSMutableString *displayString = [NSMutableString stringWithString:@"["];
    for (NSInteger i = 0; i < array.count; i++)
    {
        i == array.count - 1 ? [displayString appendString:[NSString stringWithFormat:@"%ld", (long)[array[i] integerValue]]] :[displayString appendString:[NSString stringWithFormat:@"%ld%@", (long)[array[i] integerValue], @","]];
    }
    [displayString appendString:@"]"];
    NSLog(@"%@", displayString);
}

代码执行结果如下：
2019-05-08 01:00:11.814 20190507_sort[14548:4259814] [1,14,4,38,26,9,101,7]
2019-05-08 01:00:11.815 20190507_sort[14548:4259814] [1,4,14,38,26,9,101,7]
2019-05-08 01:00:11.815 20190507_sort[14548:4259814] [1,4,9,38,26,14,101,7]
2019-05-08 01:00:11.816 20190507_sort[14548:4259814] [1,4,7,38,26,14,101,9]
2019-05-08 01:00:11.816 20190507_sort[14548:4259814] [1,4,7,26,38,14,101,9]
2019-05-08 01:00:11.816 20190507_sort[14548:4259814] [1,4,7,14,38,26,101,9]
2019-05-08 01:00:11.816 20190507_sort[14548:4259814] [1,4,7,9,38,26,101,14]
2019-05-08 01:00:11.816 20190507_sort[14548:4259814] [1,4,7,9,26,38,101,14]
2019-05-08 01:00:11.817 20190507_sort[14548:4259814] [1,4,7,9,14,38,101,26]
2019-05-08 01:00:11.817 20190507_sort[14548:4259814] [1,4,7,9,14,26,101,38]
2019-05-08 01:00:11.817 20190507_sort[14548:4259814] [1,4,7,9,14,26,38,101]
2019-05-08 01:00:11.817 20190507_sort[14548:4259814] 共执行了11次

发现结果是对的，但未按照冒泡定义的顺序执行。在第一次循环完成后101并未到达最末尾。

好接下来重新修改代码：

-(NSArray*)bubbleSort:(NSArray*)array
{
    NSMutableArray *sortArray = [NSMutableArray arrayWithArray:array];
    NSInteger execCount = 0;//交换次数
    NSInteger forCount = 0;//for循环总共执行了多少次
    for (NSInteger i = 0; i < sortArray.count; i++)
    {
        forCount++;
        for (NSInteger j = 0; j < sortArray.count - 1; j++)
        {
            forCount++;
            if ([sortArray[j] integerValue] > [sortArray[j + 1] integerValue])
            {
                [sortArray exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
                execCount++;
                [self displayArray:sortArray];
            }
        }
    }
    NSLog(@"交换共执行了%ld次", execCount);
    NSLog(@"for循环共执行了%ld次", forCount);
    return sortArray;
}

代码执行结果如下：
2019-05-08 11:29:36.501 20190507_sort[14910:4308910] [4,1,14,38,26,9,101,7]
2019-05-08 11:29:36.502 20190507_sort[14910:4308910] [4,1,14,26,38,9,101,7]
2019-05-08 11:29:36.502 20190507_sort[14910:4308910] [4,1,14,26,9,38,101,7]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [4,1,14,26,9,38,7,101]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [1,4,14,26,9,38,7,101]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [1,4,14,9,26,38,7,101]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [1,4,14,9,26,7,38,101]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [1,4,9,14,26,7,38,101]
2019-05-08 11:29:36.503 20190507_sort[14910:4308910] [1,4,9,14,7,26,38,101]
2019-05-08 11:29:36.504 20190507_sort[14910:4308910] [1,4,9,7,14,26,38,101]
2019-05-08 11:29:36.504 20190507_sort[14910:4308910] [1,4,7,9,14,26,38,101]
2019-05-08 11:29:36.504 20190507_sort[14910:4308910] 交换共执行了11次
2019-05-08 11:29:36.504 20190507_sort[14910:4308910] for循环共执行了64次

由此可以看到完全符合了冒泡排序的定义的代码就完成了，但是各位看官有没有可以觉得改进的地方呢？

//在内循环处我们可以将：
for (NSInteger j = 0; j < sortArray.count - 1; j++)
//修改为
for (NSInteger j = 0; j < sortArray.count - 1 - i; j++)
//因为每完成一次内循环，就会将最大的数排到最后，最后的数字已经是经过排序的，无需再次进行排序。
2019-05-08 11:30:46.058 20190507_sort[14933:4310457] [4,1,14,38,26,9,101,7]
2019-05-08 11:30:46.059 20190507_sort[14933:4310457] [4,1,14,26,38,9,101,7]
2019-05-08 11:30:46.059 20190507_sort[14933:4310457] [4,1,14,26,9,38,101,7]
2019-05-08 11:30:46.059 20190507_sort[14933:4310457] [4,1,14,26,9,38,7,101]
2019-05-08 11:30:46.059 20190507_sort[14933:4310457] [1,4,14,26,9,38,7,101]
2019-05-08 11:30:46.060 20190507_sort[14933:4310457] [1,4,14,9,26,38,7,101]
2019-05-08 11:30:46.060 20190507_sort[14933:4310457] [1,4,14,9,26,7,38,101]
2019-05-08 11:30:46.060 20190507_sort[14933:4310457] [1,4,9,14,26,7,38,101]
2019-05-08 11:30:46.060 20190507_sort[14933:4310457] [1,4,9,14,7,26,38,101]
2019-05-08 11:30:46.060 20190507_sort[14933:4310457] [1,4,9,7,14,26,38,101]
2019-05-08 11:30:46.061 20190507_sort[14933:4310457] [1,4,7,9,14,26,38,101]
2019-05-08 11:30:46.061 20190507_sort[14933:4310457] 交换共执行了11次
2019-05-08 11:30:46.061 20190507_sort[14933:4310457] for循环共执行了36次
//可以看到for循环执行了36次，比上面的64次大大减少

那我们这个就是完美的了吗，肯定不是，我们可以考虑到如果一次循环根本没有走任何交换，那说明排序已经按照要求成功了，剩下未走完的循环就不需要了。

//我们需要添加一个变量进行控制
-(NSArray*)bubbleSort:(NSArray*)array
{
    NSMutableArray *sortArray = [NSMutableArray arrayWithArray:array];
    NSInteger execCount = 0;//交换次数
    BOOL bFlag = YES;//是否已经是排序完成
    NSInteger forCount = 0;//for循环总共执行了多少次
    for (NSInteger i = 0; i < sortArray.count && bFlag; i++)
    {
        bFlag = NO;
        forCount++;
        for (NSInteger j = 0; j < sortArray.count - 1 - i; j++)
        {
            forCount++;
            if ([sortArray[j] integerValue] > [sortArray[j + 1] integerValue])
            {
                [sortArray exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
                execCount++;
                bFlag = YES;
                [self displayArray:sortArray];
            }
        }
    }
    NSLog(@"交换共执行了%ld次", execCount);
    NSLog(@"for循环共执行了%ld次", forCount);
    return sortArray;
}
//执行结果如下：
2019-05-08 11:34:16.036 20190507_sort[14963:4312855] [4,1,14,38,26,9,101,7]
2019-05-08 11:34:16.037 20190507_sort[14963:4312855] [4,1,14,26,38,9,101,7]
2019-05-08 11:34:16.037 20190507_sort[14963:4312855] [4,1,14,26,9,38,101,7]
2019-05-08 11:34:16.037 20190507_sort[14963:4312855] [4,1,14,26,9,38,7,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,14,26,9,38,7,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,14,9,26,38,7,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,14,9,26,7,38,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,9,14,26,7,38,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,9,14,7,26,38,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,9,7,14,26,38,101]
2019-05-08 11:34:16.038 20190507_sort[14963:4312855] [1,4,7,9,14,26,38,101]
2019-05-08 11:34:16.039 20190507_sort[14963:4312855] 交换共执行了11次
2019-05-08 11:34:16.039 20190507_sort[14963:4312855] for循环共执行了33次
//可以看到，没有添加变量之前是36次，添加了变量是33次，减少了3次

我们继续思考，程序还有没有需要改进的地方，我们程序的健壮性如何？我们考虑调用的时候传进来的是空数组或者数组只有一个数据的情况了吗？

//我们应该在函数的开始去判断数组的状态已经长度
-(NSArray*)bubbleSort:(NSArray*)array
{
    //判断数组状态
    if (!array || array.count == 1)
    {
        return array;
    }
    NSMutableArray *sortArray = [NSMutableArray arrayWithArray:array];
    NSInteger execCount = 0;//交换次数
    BOOL bFlag = YES;//是否已经是排序完成
    NSInteger forCount = 0;//for循环总共执行了多少次
    for (NSInteger i = 0; i < sortArray.count && bFlag; i++)
    {
        bFlag = NO;
        forCount++;
        
        for (NSInteger j = 0; j < sortArray.count - 1 - i; j++)
        {
            forCount++;
            if ([sortArray[j] integerValue] > [sortArray[j + 1] integerValue])
            {
                [sortArray exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
                execCount++;
                bFlag = YES;
                [self displayArray:sortArray];
            }
        }
    }
    NSLog(@"交换共执行了%ld次", execCount);
    NSLog(@"for循环共执行了%ld次", forCount);
    return sortArray;
}

至此，一个相对稳定的冒泡算法程序已经完成了。
在排序算法中，冒泡排序的算法的时间复杂度为O(n²)，这是一个很耗时的算法，那我们为什么还要费劲去实现它呢，其实我们要侧重于它的优化过程，思考在自己的项目中代码能不能进一步的优化，代码是否够健壮？只有不断的执行一个一个PDCA循环，才能保证我们代码的质量。
本人小菜一枚，在这里班门弄斧，抛砖引玉，文中如果有错误的地方请大家指正，共同进步！

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,491评论 5赞 459
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,856评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,745评论 0赞 319
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,196评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,073评论 4赞 355
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,112评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,531评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,215评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,485评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,578评论 2赞 309
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,356评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,215评论 3赞 312
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,583评论 3赞 299
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,898评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,174评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,497评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,697评论 2赞 335

iOS之你写出了一个真正的冒泡排序吗？

推荐阅读更多精彩内容