文档章节

iOS冒泡排序

zh_iOS
 zh_iOS
发布于 2018/02/06 15:18
字数 895
阅读 32
收藏 2

冒泡排序算法顾名思义,经过每一次排序算法之后,最大的泡泡(数)会飘到最上面,第二次排序之后,第二大的泡泡(数)飘到倒数第二的位置 ..... 以此类推,直至完成从小到大的排序。

冒泡排序原理:

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

用图片表示冒泡排序的过程更直观:

依照冒泡排序的概念可以方便的写出排序的实现:

- (void)bubbleSort:(NSMutableArray *)arr {
    int count = 0;
    int cycleCount = 0;
    for (int i = 0; i<arr.count-1; i++) {
        cycleCount += 1;
        // 每次循环都不需要比较最后一个,倒数第二个,倒数第三个... 所以二层循环最好减去已经排好序的数
        for (int j = 0; j<arr.count-i-1; j++) {
            cycleCount += 1;
            if ([arr[j] integerValue] > [arr[j+1] integerValue]) {
                NSInteger temp = [arr[j] integerValue];
                arr[j] = arr[j+1];
                arr[j+1] = @(temp);
                count += 1;
            }
        }
    }
    NSLog(@"交换次数-->%@",@(count));
    NSLog(@"循环次数-->%@",@(cycleCount));
    NSLog(@"%@",arr);
}

上面的方式是最原始的排序,再次基础上可以对冒泡排序进行优化 。

冒泡排序的主要操作就是不断的循环比较然后交换两个大小不同的数的位置。 如果要正确的排序交换的次数肯定是固定的,这个是不能减少的,那就从循环比较上进行优化 。 

用一个变量进行记录,记录在一次循环中是否发生了交换,如果没有则说明这个序列已经是有序的了,则退出循环。

- (void)bubbleSort:(NSMutableArray *)arr {
    int count = 0;
    int cycleCount = 0;
    for (int i = 0; i<arr.count-1; i++) {
        cycleCount += 1;
        finished = YES;
        for (int j = 0; j<arr.count-i-1; j++) {
            cycleCount += 1;
            if ([arr[j] integerValue] > [arr[j+1] integerValue]) {
                NSInteger temp = [arr[j] integerValue];
                arr[j] = arr[j+1];
                arr[j+1] = @(temp);
                finished = NO;
                count += 1;
            }
        }
        if (finished) break;
    }
    NSLog(@"----交换次数为%@",@(count));
    NSLog(@"----循环次数为%@",@(cycleCount));
    NSLog(@"%@",arr);
}

仔细研究冒泡排序的原理可以发现,还可以再次基础上进行优化。 记录每一次内层循环排序最后发生位置交换的位置K,这个位置之后的都已经是有序的了,下次排序内层循环只需要排序前 0--K 个数即可 。

- (void)bubbleSort3:(NSMutableArray *)arr {
    int count = 0;
    int cycleCount = 0;
    int pos = (int)arr.count-1;
    for (int i = 0; i<arr.count-1; i++) {
        finished = YES;
        cycleCount += 1;
        int currentPos = 0;
        // 从上一次发生交换的位置开始循环
        for (int j = 0; j<pos; j++) {
            cycleCount += 1;
            if ([arr[j] integerValue] > [arr[j+1] integerValue]) {
                NSInteger temp = [arr[j] integerValue];
                arr[j] = arr[j+1];
                arr[j+1] = @(temp);
                count += 1;
                // 记录发生交换的位置
                currentPos = j;
                finished = NO;
            }
        }
        pos = currentPos;
        if (finished) break;
    }
    NSLog(@"交换次数-->%@",@(count));
    NSLog(@"循环次数-->%@",@(cycleCount));
    NSLog(@"%@",arr);
}

时间复杂度:

冒泡排序需要进行两层循环,最坏的情况是:序列正好是倒序的,这种情况是O(n²),最好的情况是:序列正好的是正序的,这种情况是:O(n) .平均时间复杂度是O(n²)。

由于时间复杂度是平方级的,所以冒泡排序一般适用于小序列排序 。序列小(如:长度在20个以内)的情况下冒泡排序是比快排的速度还要快的。

© 著作权归作者所有

共有 人打赏支持
zh_iOS
粉丝 28
博文 73
码字总数 34061
作品 0
石景山
程序员
私信 提问
iOS个人中心渐变动画、微信对话框、标签选择器、自定义导航栏、短信验证输入框等源码

iOS精选源码 简单的个人中心页面-自定义导航栏并予以渐变动画(http://www.code4app.com/thread-10860-1-1.html) 程序员取悦女票的正确姿势---Tip1(iOS美容篇)(http://www.code4app.com/th...

Android爱开源
01/16
0
0
2018 iOS 面试题大全(补充完整版)

原文地址:2018 iOS 面试题大全 由于原作者并没有继续更新,这里我转过来继续更新下 这个栏目将持续更新--请iOS的小伙伴关注! 1、iOS 应用导航模式有哪些? 2、iOS 中持久化方式有哪些? 3、...

Theendisthebegi
2018/11/15
0
0
苹果发布 iOS 9.2 正式版:多项功能增强、改进

除了发布 OS X 10.11.2 和 tvOS 9.1 正式版外,苹果今天还发布了 iOS 9.2 正式版。iOS 9.2 是自 iOS 9 在今年9月发布之后的第二次重大版本更新。iOS 9.2 测试开始于10月底,开发者和公测用户...

oschina
2015/12/09
3.8K
22
IOS学习,最简单的表格应用程序,学习,列出博客

IOS编程浅蓝教程,这是博客地址http://www.cnblogs.com/haichao/category/425378.html IOS编程浅蓝教程:锲子 IOS编程浅蓝教程(一)先决条件:开始iOS编程的必要准备 IOS编程浅蓝教程(二) Hel...

andy521zhu
2015/01/17
0
0
苹果关闭 iOS 7.1.2 验证,降级不再可能

今天,苹果正式关闭了 iOS 7.1.2 固件验证,这意味着用户从 iOS 8 降级至 iOS 7 将无法完成验证。对于 iOS 8 以及 iOS 8.0.1 不满意的用户将无法降级至 iOS 7.1.2。苹果决定现在停止 iOS 7....

oschina
2014/09/27
3.9K
19

没有更多内容

加载失败,请刷新页面

加载更多

python中类方法和静态方法区别

面相对象程序设计中,类方法和静态方法是经常用到的两个术语。 逻辑上讲:类方法是只能由类名调用;静态方法可以由类名或对象名进行调用。 在C++中,静态方法与类方法逻辑上是等价的,只有一...

xiangyunyan
今天
9
0
Hibernate SQLite方言

以下代码有参考过github上国外某位大佬的,在发文的最新稳定版Hibernate上是可用的,有时间再仔细分析一下 import org.hibernate.dialect.Dialect;import org.hibernate.dialect.function.S...

CHONGCHEN
今天
4
0
CentOS 7 MariaDB搭建主从服务器

本文编写环境为CentOS7。确保关闭SELinux,关闭防火墙或者防打开指定端口。具体信息如下 #master[root@promote ~]# cat /etc/redhat-release CentOS Linux release 7.6.1810 (Core) [r...

白豆腐徐长卿
今天
11
0
介绍python中运算符优先级

下面这个表给出Python的运算符优先级,从最低的优先级(最松散地结合)到最高的优先级(最紧密地结合)。这意味着在一个表达式中,Python会首先计算表中较下面的运算符,然后在计算列在表上部...

问题终结者
今天
4
0
Spring Boot 2.x基础教程:快速入门

简介 在您第1次接触和学习Spring框架的时候,是否因为其繁杂的配置而退却了?在你第n次使用Spring框架的时候,是否觉得一堆反复黏贴的配置有一些厌烦?那么您就不妨来试试使用Spring Boot来让...

程序猿DD
昨天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部