iOS算法总结-冒泡排序

百家 作者:iOS开发 2017-10-21 14:48:18 阅读:463

点击上方“iOS开发”,选择“置顶公众号”

关键时刻,第一时间送达!


冒泡排序(Bubble Sort): 一种交换排序,它的基本思想是:两两比较相邻的关键字,如果反序则交换,直到没有反序的记录为止。


平实写冒泡排序,我都是这么写的:


- (void)logArray {

    NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;

    for (int i = 0; i < arr.count; i++) {

        for (int j = i+1; j < arr.count; j++) {

            if (arr[i] < arr[j]) {

                [arr exchangeObjectAtIndex:i withObjectAtIndex:j];

            }

        }

        [self logArr:arr];

    }

}

//打印数组

- (void)logArr:(NSMutableArray * )array {

    NSString * str = @"";

    for (NSNumber * value in array) {

       str = [str stringByAppendingString:[NSString stringWithFormat:@"%zd ",[value integerValue]]];

    }

    NSLog(@"%@",str);

}

//打印结果如下

16 1 2 9 7 12 5 3 8 13 10

16 13 1 2 7 9 5 3 8 12 10

16 13 12 1 2 7 5 3 8 9 10

16 13 12 10 1 2 5 3 7 8 9

16 13 12 10 9 1 2 3 5 7 8

16 13 12 10 9 8 1 2 3 5 7

16 13 12 10 9 8 7 1 2 3 5

16 13 12 10 9 8 7 5 1 2 3

16 13 12 10 9 8 7 5 3 1 2

16 13 12 10 9 8 7 5 3 2 1

16 13 12 10 9 8 7 5 3 2 1


查了定义后发现,这不算是标准的冒牌排序算法,因为它不满足“两两比较相邻”的冒泡排序思想,它更应该是最最简单的交换排序而已。它的思路是让每个关键字,都和它后面的一个关键字比较,如果小则交换。


它应该算是最容易写的排序代码了,不过这个简单易懂的代码是有缺陷的,观察后发现,每次排序只能确定一个位置,直到倒数第二次 末尾的最小值1才显示到最后,也就是说,这个算法的效率是非常低的。


正宗的冒泡排序算法:


- (void)logArrayFunction {

    int count  = 0;

    int forcount  = 0;

    NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;

    

    for (int i = 0; i < arr.count; i++) {

        forcount++;

        for (int j = (int)arr.count-2; j >= i; j--) {

            count++;

            if (arr[j] < arr[j+1]) {

                [arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];

            }

        }

        [self logArr:arr];

    }

    NSLog(@"循环次数:%d",forcount);

    NSLog(@"共%d次比较",count);

}

//打印如下

16 13 1 2 9 7 12 5 3 8 10

16 13 12 1 2 9 7 10 5 3 8

16 13 12 10 1 2 9 7 8 5 3

16 13 12 10 9 1 2 8 7 5 3

16 13 12 10 9 8 1 2 7 5 3

16 13 12 10 9 8 7 1 2 5 3

16 13 12 10 9 8 7 5 1 2 3

16 13 12 10 9 8 7 5 3 1 2

16 13 12 10 9 8 7 5 3 2 1

16 13 12 10 9 8 7 5 3 2 1

16 13 12 10 9 8 7 5 3 2 1

循环次数:11

共55次比较


冒泡排序的优化:


设想如果待排序的序列是{2,1,3,4,5,6,7,8,9},也就是说,2和1交换后就属于正常的排序结果了,但是之后的大量比较还是大大多余了。为了不再继续后面的循环判断工作,我们需要改进下代码,增加个BOOL变量flag来实现这一算法的改进。


- (void)logArrayFunctionNice {

    int count  = 0;

    int forcount  = 0;

    BOOL flag = YES;

    NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;

    

    for (int i = 0; i < arr.count && flag; i++) {

        forcount++;

        flag = NO;

        for (int j = (int)arr.count-2; j > i; j--) {

            count++;

            if (arr[j] < arr[j+1]) {

                [arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];

                flag = YES;

            }

        }

        [self logArr:arr];

    }

    NSLog(@"循环次数:%d",forcount);

    NSLog(@"共%d次比较",count);

}

//打印

16 13 1 2 9 7 12 5 3 8 10

16 13 12 1 2 9 7 10 5 3 8

16 13 12 10 1 2 9 7 8 5 3

16 13 12 10 9 1 2 8 7 5 3

16 13 12 10 9 8 1 2 7 5 3

16 13 12 10 9 8 7 1 2 5 3

16 13 12 10 9 8 7 5 1 2 3

16 13 12 10 9 8 7 5 3 1 2

16 13 12 10 9 8 7 5 3 2 1

16 13 12 10 9 8 7 5 3 2 1

循环次数:10

共45次比较



  • 作者: 方圆一里

  • 链接:http://www.jianshu.com/p/e3294692966e

  • 來源:简书

  • iOS开发整理发布,转载请联系作者授权

【点击成为安卓大神】

关注公众号:拾黑(shiheibook)了解更多

[广告]赞助链接:

四季很好,只要有你,文娱排行榜:https://www.yaopaiming.com/
让资讯触达的更精准有趣:https://www.0xu.cn/

公众号 关注网络尖刀微信公众号
随时掌握互联网精彩
赞助链接