美文网首页
iOS之你写出了一个真正的冒泡排序吗？

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

作者: 乐一游 | 来源:发表于2019-05-08 11:55 被阅读0次

    冒泡排序的定义如下：
    它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从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循环，才能保证我们代码的质量。
    本人小菜一枚，在这里班门弄斧，抛砖引玉，文中如果有错误的地方请大家指正，共同进步！

    相关文章

      网友评论

          本文标题：iOS之你写出了一个真正的冒泡排序吗？

          本文链接：https://www.haomeiwen.com/subject/xwqpoqtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|iOS之你写出了一个真正的冒泡排序吗？|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！