排序算法三:冒泡排序

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
615
文章
12
评论
2018年3月3日23:53:30 评论

一、原理

冒泡排序的原理很简单, 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从从Z到A)错误就把他们交换过来。 冒泡排序是一种稳定的排序算法。

冒泡排序不管在什么情况下,时间复杂度都是O(\(n^2\))。

对比插入排序来说,在平均的情况下,插入排序性能是冒泡排序的两倍。

图例:

以数组[54, 15, 34, 82, 15, 46, 85, 43]为例:

排序算法三:冒泡排序

第一次循环先比较54和15,54大于15,交换两个元素:

排序算法三:冒泡排序

比较54和34,54大于34,交换两个元素:

排序算法三:冒泡排序

比较54和82,54不大于82,不交换:

排序算法三:冒泡排序

比较82和15,82大于15,交换两个元素:

排序算法三:冒泡排序

按照相同的方式一直对比,直到最后,85被移动到最后:

排序算法三:冒泡排序

此时完成一轮冒泡排序,接下来将剩下的元素再次执行同样的操作即可完成对整个数组的排序。

二、代码实现

2.1 C++实现

2.2 python实现

三、冒泡排序的优化

当对第x个数据排序时,冒泡排序每次都会遍历剩下的n-x个元素,即使整个序列已经有序。

因此可以在这一个层面进行优化,如果序列已经有序了,则后面的排序就无需进行了,可以添加一个标记字段来处理这个问题。

历史上的今天
3月
3
马谦马谦马谦
  • 本文由 发表于 2018年3月3日23:53:30
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/bubble-sort.html
排序算法四:梳排序 数据结构和算法

排序算法四:梳排序

一、梳排序简介 梳排序是冒泡排序的一种优化方案,主要是为了解决冒泡排序中的尾部小数值问题。它主要的思想是通过比较元素和固定步长位置上的数据,先进行部分优化,然后逐步减少步长,以此来对数据进行预处理。 ...
排序算法五:堆排序 数据结构和算法

排序算法五:堆排序

一、堆排序原理 通过最大堆的性质可以知道:一个堆中最大的元素总是在堆顶的,即数组下标0的位置。基于这一点,我们可以每次都把堆中的最大值提取出来,放到当前数组的后面。然后重新构建最大堆,重复这个过程,以...
排序算法七:计数排序 数据结构和算法

排序算法七:计数排序

一、计数排序 其基本思想为:假设n个输入的元素中的每一个都是在0到k之间的一个整数,对于每一个输入元素x,确定小于x的元素个数,直接把x放在它输出的数组中的位置上。例如有17个元素小于x,则x就应该在...
排序算法二:选择排序 数据结构和算法

排序算法二:选择排序

一、原理 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: