算法之旅 | 冒泡排序法

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 条评论
登录 后参与评论

相关文章

来自专栏技术之路

sqlserver 的事务和c#的事务

sql的事务 1 sql 2 create database model 3 go 4 use model 5 go 6 create table ...

1909
来自专栏自由而无用的灵魂的碎碎念

小项目分享---混色器

编写代码的同志们一般懂美术的就少了,偶也是,什么色轮、三维加色等等。虽然看过一些书籍(如内田广由纪的《配色基础原理》),不过还是一知半解的。

963
来自专栏hbbliyong

socket 通信 多线程调用窗体(委托)的几个知识点,记录在案,以备查阅

1.socket 通信传输汉字的方法:Encoding.GetEncoding("GB2312").GetString(Receivebyte) 发送接收都这样...

2737
来自专栏菩提树下的杨过

基于sliverlight + wcf的web 文字版IM 示例

演示地址: http://task.24city.com/default.html 预览界面: ? 一、布局 采用Grid布局,5行2列 第一行:为登录/注册信...

3226
来自专栏c#开发者

about store RecordField submit emptystring issue

operate screenshot When click save button submit to change,trace store before...

3447
来自专栏张善友的专栏

通过SmtpClient发送Exchange会议邮件

看到C#中调用Outlook API 发起会议 ,这个完全可以用SMTP方式实现的,下面我的项目中使用的代码: 对于.NET而言,从2.0开始,发邮件已经是一件...

1929
来自专栏跟着阿笨一起玩NET

treeview 绑定文件夹和文件

441
来自专栏张善友的专栏

弹出式模态窗体选择文本控件

2006年就要到来了,最近比较忙,很少更新blog,今天发一个模态窗体选择文本控件辞旧迎新.新年在发几个asp.net2.0 webPart控件同各位分享: ...

1907
来自专栏码匠的流水账

zuul自定义SimpleHostRoutingFilter

zuul的SimpleHostRoutingFilter主要用来转发不走eureka的proxy,里头是使用httpclient来转发请求的,但是有时候我们需要...

1272
来自专栏跟着阿笨一起玩NET

从sql server 中读取二进制图片

391

扫码关注云+社区