搜索
首页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
C++中的众数函数详解C++中的众数函数详解Nov 18, 2023 pm 03:08 PM

C++中的众数函数详解在统计学中,众数指的是一组数据中出现次数最多的数值。在C++语言中,我们可以通过编写一个众数函数来找到任意一组数据中的众数。众数函数的实现可以采用多种不同的方法,下面将详细介绍其中两种常用的方法。第一种方法是使用哈希表来统计每个数字出现的次数。首先,我们需要定义一个哈希表,将每个数字作为键,出现次数作为值。然后,对于给定的数据集,我们遍

C++中的取余函数详解C++中的取余函数详解Nov 18, 2023 pm 02:41 PM

C++中的取余函数详解在C++中,取余运算符(%)用于计算两个数相除的余数。它是一种二元运算符,其操作数可以是任何整数类型(包括char、short、int、long等),也可以是浮点数类型(如float、double)。取余运算符返回的结果与被除数的符号相同。例如,对于整数的取余运算,我们可以使用以下代码来实现:inta=10;intb=3;

Vue.nextTick函数用法详解及在异步更新中的应用Vue.nextTick函数用法详解及在异步更新中的应用Jul 26, 2023 am 08:57 AM

Vue.nextTick函数用法详解及在异步更新中的应用在Vue开发中,经常会遇到需要进行异步更新数据的情况,比如在修改DOM后需要立即更新数据或者在数据更新后需要立即进行相关操作。而Vue提供的.nextTick函数就是为了解决这类问题而出现的。本文就会详细介绍Vue.nextTick函数的用法,并结合代码示例来说明它在异步更新中的应用。一、Vue.nex

php-fpm调优方法详解php-fpm调优方法详解Jul 08, 2023 pm 04:31 PM

PHP-FPM是一种常用的PHP进程管理器,用于提供更好的PHP性能和稳定性。然而,在高负载环境下,PHP-FPM的默认配置可能无法满足需求,因此我们需要对其进行调优。本文将详细介绍PHP-FPM的调优方法,并给出一些代码示例。一、增加进程数默认情况下,PHP-FPM只启动少量的进程来处理请求。在高负载环境下,我们可以通过增加进程数来提高PHP-FPM的并发

Django框架中的缓存机制详解Django框架中的缓存机制详解Jun 18, 2023 pm 01:14 PM

在Web应用程序中,缓存通常是用来优化性能的重要手段。Django作为一款著名的Web框架,自然也提供了完善的缓存机制来帮助开发者进一步提高应用程序的性能。本文将对Django框架中的缓存机制进行详解,包括缓存的使用场景、建议的缓存策略、缓存的实现方式和使用方法等方面。希望对Django开发者或对缓存机制感兴趣的读者有所帮助。一、缓存的使用场景缓存的使用场景

PHP function_exists()函数用法详解PHP function_exists()函数用法详解Jun 27, 2023 am 10:32 AM

在PHP开发中,有时我们需要判断某个函数是否可用,这时我们便可以使用function_exists()函数。本文将详细介绍function_exists()函数的用法。一、什么是function_exists()函数?function_exists()函数是PHP自带的一个内置函数,用于判断某个函数是否被定义。该函数返回一个布尔值,如果函数存在返回True,

PHP strpos()函数用法详解PHP strpos()函数用法详解Jun 27, 2023 am 10:43 AM

PHPstrpos()函数用法详解在PHP编程中,字符串处理是非常重要的一部分。PHP通过提供一些内置函数来实现字符串处理。其中,strpos()函数就是PHP中最常用的一个字符串函数之一。该函数的目的是在一个指定的字符串中搜索另一个指定字符串的位置,如果包含则返回这个位置,否则返回false。本文将通过详细分析PHPstrpos()函数的用法,助你更好

Gin框架的模板渲染功能详解Gin框架的模板渲染功能详解Jun 22, 2023 pm 10:37 PM

Gin框架是目前非常流行的Go语言Web框架之一。作为一个轻量级的框架,Gin提供了丰富的功能和灵活的架构,使得它在Web开发领域中备受欢迎。其中一个特别重要的功能是模板渲染。在本文中,我们将介绍Gin框架的模板渲染功能,并深入了解它的实现原理。一、Gin框架的模板渲染功能Gin框架使用了多种模板渲染引擎来构建Web应用程序。目前,它支持以下几种模板引擎:

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脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前By尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

DVWA

DVWA

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

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

EditPlus 中文破解版

EditPlus 中文破解版

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

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版