算法之旅 | 冒泡排序法

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

相关文章

来自专栏python读书笔记

《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

22160
来自专栏我是攻城师

为什么快速排序算法效率比较高?

快速排序算法是非常高效的一个排序算法,在众多的排序算法里面其无论在时间复杂度还是空间复杂度都是比较低的。因此作为一个程序员,我们很有必要学习和理解快排的原理。

2.9K30
来自专栏C语言C++游戏编程

C语言内置运算符丰富到令人头皮发麻,C语言基础教程之运算符篇

运算符是告诉编译器执行特定数学或逻辑函数的符号。C语言内置运算符丰富,并提供以下类型的运算符 -

13810
来自专栏包子铺里聊IT

How to calculate “hard” runtime complexity?

在技术面试中,准确说出一个解法的runtime complexity(算法时间复杂度)是一个非常重要的点。考虑到对于算法时间复杂度的理解是CS领域的基础,因此这...

29780
来自专栏xingoo, 一个梦想做发明家的程序员

大整数乘法

                                                                                ...

24450
来自专栏绿巨人专栏

Category Theory: 01 One Structured Family of Structures

\(G = \{ G, +, e \}\),一个数据集\(G\),一个二元操作符\(+\),和一个幺元\(e\)。

13730
来自专栏落影的专栏

程序员进阶之算法练习(十七)

前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 如何从这篇文章受益? 先看题目大意,对照Example的样...

45890
来自专栏Lambda

JavaScript排序算法详解

JS家的排序算法 引子 有句话怎么说来着: 雷锋推倒雷峰塔,Java implements JavaScript. 当年,想凭借抱Java大腿火一把...

33580
来自专栏我和我大前端的故事

数据结构学习☞入门(一)算法数据结构

编程如果只是一个为了解决生活温饱的工具,那你可以完全忽略数据结构,算法,你的目标很容易实现;但如果你是热爱编程,把它当做对生活的追求,想在这一行走的更远,更久,...

11330
来自专栏开发与安全

算法:快速排序以及第k小元素的线性选择算法

简要介绍下快速排序的思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行...

249100

扫码关注云+社区

领取腾讯云代金券