算法之旅 | 冒泡排序法

HTML5学堂-码匠:本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单,容易上手,稳定性也比较高, 算是一种较好理解的算法,也是面试官高频提问的算法之一。

Tips:关于“算法”及“排序”的基础知识,在此前“选择排序法”中已详细讲解,可点击文后的相关文章链接查看,在此不再赘述。

冒泡排序法的原理

基本原理

从序列头部开始遍历,两两比较,如果前者比后者大,则交换位置,直到最后将最大的数(本次排序最大的数)交换到无序序列的尾部,从而成为有序序列的一部分;

下次遍历时,此前每次遍历后的最大数不再参与排序;

多次重复此操作,直到序列排序完成。

由于在排序的过程中总是小数往前放,大数往后放,类似于气泡逐渐向上漂浮,所以称作冒泡排序。

原理图解

Tips:蓝色代表在一轮排序中等待交换,黑色代表在该轮排序中已交换完成,红色代表已排序完成

实现冒泡的步骤分解

使用for循环确定排序次数

由于待排序的序列只剩下一个数时已经能够确定顺序,则无需进行排序,因此,排序次数为序列长度 – 1。

每次排序的比较次数控制

每次排序,序列中的多个数字要分别进行两两比较,多次的比较需要利用for语句来进行实现。该for循环嵌套于排序次数的for循环当中(形成双for的嵌套)。

Tips:j 需要设置为小于 len - i - 1,减i的原因是已经排序完成的数不再参与比较,减1的原因是数组下标索引值从0开始。

核心功能 — 两两比较并根据情况交换位置

比较两数大小,如果前者比后者大,则进行数值的交换,也就是交换位置。

冒泡排序法完整代码

冒泡排序法的优化

假如序列的数据为:[0, 1, 2, 3, 4, 5];

使用上面的冒泡排序法进行排序,得到的结果肯定没有问题,但是,待排序的序列是有序的,理论上是无需遍历排序。

当前的算法不管初始的序列是否有序,都会进行遍历排序,效率会比较低,因此需要优化当前的排序算法。

在如下的算法中,引入一个swap变量,每一次排序之前初始化为false;若发生两数交换位置,则将其设置为true。

在每次排序结束时候判断swap是否为false,如果是,则说明序列已排序完成或者序列本身是有序序列,就不再进行下一次排序。

通过此方法,减少不必要的比较和位置交换,进一步提高算法的性能。

冒泡排序法的效率

时间复杂度

最佳状态:待排序的序列本身是有序序列,排序次数根据优化后的代码,可以得出是n-1次,时间复杂度为O(n);

最坏的情况:待排序的序列是逆序的,此时需要排序1 + 2 +3 ……(n - 1) = n(n – 1 )/2次,

时间复杂度为O(n^2)。

空间复杂度

冒泡排序法需要一个额外空间(temp变量)来交换元素的位置,所以空间复杂度为O(1)。

算法的稳定性

当相邻元素相等时,并不需要交换位置,也就不会出现相同元素的前后顺序发生改变,所以,是稳定性排序。

O是个啥?!

时间复杂度,更准确的说该是描述一个算法在问题规模不断增大时对应的时间增长曲线。所以,这些增长数量级并不是一个准确的性能评价,可以理解为一个近似值。(空间复杂度同理)

O(n²)表示当n很大的时候,复杂度约等于Cn²,C是某个常数,简单说就是当n足够大的时候,随着n的线性增长复杂度将沿平方增长。

O(n)表示,n很大的时候复杂度约等于Cn,C是某个常数。简言之:随着n的线性增长,复杂度沿线性级别增长。

O(1)表示,n很大的时候,复杂度基本就不增长了。简言之:随着n的线性增长,复杂度不受n的影响,沿常数级别增长(此处的常数是1)。

Tips:图中O(1)紧贴着X轴,并看不太清楚。

Tips:该图来源于“Stack Overflow”网站。

开开心心每一天

生活艰辛,代码不易,但,不要忘记微笑!

版权声明:该图来自“【美】莉兹·克里莫 (author)”的书籍《你今天真好看》

原文发布于微信公众号 - HTML5学堂(h5course-com)

原文发表时间:2017-08-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

技能 | 利用SAS进行数据清洗技术——缺失值查询

数据清洗技术是统计分析之前必做的一步,而且也是非常麻烦的一步,有时甚至花费的时间比统计分析都长。所以没有一定的技巧,这将是个非常烦人的工作。本篇文章介绍如何利用...

20010
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(01-05打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

351
来自专栏calmound

sdut 1446 超级玛丽

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1446 题意:你...

2555
来自专栏听雨堂

Pandas对行情数据的预处理

库里是过去抓取的行情数据,间隔6秒,每分钟8-10个数据不等,还有开盘前后的一些数据,用Pandas可以更加优雅地进行处理。 ? 需要把当前时间设置为index...

18910
来自专栏章鱼的慢慢技术路

牛课堂算法直播题目

1968
来自专栏算法channel

玩转Pandas,让数据处理更easy系列2

上一篇总结了Pandas中最重要的两个数据结构:Series和DataFrame,前者相当于更加强大的一维数组,是数组和字典的组合,因为既可以按照位置,也能通过...

763
来自专栏zhisheng

Java常用排序算法/程序员必须掌握的8大排序算法(下)

昨天发表的java常用排序算法/程序员必须掌握的8大算法(上),没看的可以点上面这个链接↑↑↑↑,(概念+实例+代码+排序舞蹈视频)更好的帮助你理解。 java...

4189
来自专栏程序员宝库

LCS 算法:Javascript 最长公共子序列

作者:司徒正美 链接:https://segmentfault.com/a/1190000012864957 最长公共子序列(Longest Common Su...

38810
来自专栏程序员互动联盟

【答疑解惑】C语言里面如何计算数据类型取值范围?

先看一个网友的问题: ? 初学者有不少会对数据类型的取值范围有疑问,数据类型的取值范围关系到定义合适的变量,尤其是在进行嵌入式开发时更要清楚。这里有必要介绍一下...

2516
来自专栏王肖的UT

GLSL-运算符和表达式

1473

扫描关注云+社区