搜索
首页web前端js教程冒泡排序法详解

冒泡排序法详解

Oct 06, 2017 am 10:41 AM
冒泡排序详解

冒泡排序法

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”网站。

相关文章链接

选择排序法

开开心心每一天

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

算法之旅 | 冒泡排序法 - 独行冰海 - 独行冰海

以上是冒泡排序法详解的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
Python vs. JavaScript:开发环境和工具Python vs. JavaScript:开发环境和工具Apr 26, 2025 am 12:09 AM

Python和JavaScript在开发环境上的选择都很重要。1)Python的开发环境包括PyCharm、JupyterNotebook和Anaconda,适合数据科学和快速原型开发。2)JavaScript的开发环境包括Node.js、VSCode和Webpack,适用于前端和后端开发。根据项目需求选择合适的工具可以提高开发效率和项目成功率。

JavaScript是用C编写的吗?检查证据JavaScript是用C编写的吗?检查证据Apr 25, 2025 am 12:15 AM

是的,JavaScript的引擎核心是用C语言编写的。1)C语言提供了高效性能和底层控制,适合JavaScript引擎的开发。2)以V8引擎为例,其核心用C 编写,结合了C的效率和面向对象特性。3)JavaScript引擎的工作原理包括解析、编译和执行,C语言在这些过程中发挥关键作用。

JavaScript的角色:使网络交互和动态JavaScript的角色:使网络交互和动态Apr 24, 2025 am 12:12 AM

JavaScript是现代网站的核心,因为它增强了网页的交互性和动态性。1)它允许在不刷新页面的情况下改变内容,2)通过DOMAPI操作网页,3)支持复杂的交互效果如动画和拖放,4)优化性能和最佳实践提高用户体验。

C和JavaScript:连接解释C和JavaScript:连接解释Apr 23, 2025 am 12:07 AM

C 和JavaScript通过WebAssembly实现互操作性。1)C 代码编译成WebAssembly模块,引入到JavaScript环境中,增强计算能力。2)在游戏开发中,C 处理物理引擎和图形渲染,JavaScript负责游戏逻辑和用户界面。

从网站到应用程序:JavaScript的不同应用从网站到应用程序:JavaScript的不同应用Apr 22, 2025 am 12:02 AM

JavaScript在网站、移动应用、桌面应用和服务器端编程中均有广泛应用。1)在网站开发中,JavaScript与HTML、CSS一起操作DOM,实现动态效果,并支持如jQuery、React等框架。2)通过ReactNative和Ionic,JavaScript用于开发跨平台移动应用。3)Electron框架使JavaScript能构建桌面应用。4)Node.js让JavaScript在服务器端运行,支持高并发请求。

Python vs. JavaScript:比较用例和应用程序Python vs. JavaScript:比较用例和应用程序Apr 21, 2025 am 12:01 AM

Python更适合数据科学和自动化,JavaScript更适合前端和全栈开发。1.Python在数据科学和机器学习中表现出色,使用NumPy、Pandas等库进行数据处理和建模。2.Python在自动化和脚本编写方面简洁高效。3.JavaScript在前端开发中不可或缺,用于构建动态网页和单页面应用。4.JavaScript通过Node.js在后端开发中发挥作用,支持全栈开发。

C/C在JavaScript口译员和编译器中的作用C/C在JavaScript口译员和编译器中的作用Apr 20, 2025 am 12:01 AM

C和C 在JavaScript引擎中扮演了至关重要的角色,主要用于实现解释器和JIT编译器。 1)C 用于解析JavaScript源码并生成抽象语法树。 2)C 负责生成和执行字节码。 3)C 实现JIT编译器,在运行时优化和编译热点代码,显着提高JavaScript的执行效率。

JavaScript在行动中:现实世界中的示例和项目JavaScript在行动中:现实世界中的示例和项目Apr 19, 2025 am 12:13 AM

JavaScript在现实世界中的应用包括前端和后端开发。1)通过构建TODO列表应用展示前端应用,涉及DOM操作和事件处理。2)通过Node.js和Express构建RESTfulAPI展示后端应用。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

WebStorm Mac版

WebStorm Mac版

好用的JavaScript开发工具

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。