Logic
向着梦想进发
Logic's Blog

【随笔】浅谈冒泡排序

公历十一月二十五日,也就是我发觉OJ上更了一道冒泡排序的那一天,我只在机房里探寻py之法,遇见泳良君,前来问我道:“可曾A了首题否?”我后悔万分,小声说道:“没有”。他就正告我其 $ O(n) $ 之算法,“先生明年还是继续努力吧。”

这我是明白的,但凡我写的题目,大概是因思维短路或细节错误,$ AC $ 的概率一向就甚为寥落,然而在这样的艰难前行中,毅然支持我的就有他。我也早就觉得该做些什么,写些什么了。

他又与我谈起文化课之苦恼,也一直觉得落下了什么。这一旬岁月的波涛汹涌,又在我的脑海里打转。积累了太多的想法,我终能确定有写一些什么的必要了。

但是又从何谈起呢。如同乱码一样的大脑,终究要怎么解码呢...

任何一个伟大的思想,都有一个微不足道的开始。

不如回到最初,从最基础的排序算法开始。

那就让我们从起点开始,重新学习,重新开始吧。

冒泡排序

冒泡排序(英语:Bubble sort)是一种简单的排序算法。由于在算法的执行过程中,较小的元素像是气泡般慢慢「浮」到数列的顶端,故叫做冒泡排序。——OI wiki 如是说

作为最简单的排序算法之一,冒泡排序就像 $ Abandon $ 在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。

总之在一个绝对接触不到水的课程上,这确乎是一个非常 $ 水 $ 的算法了。

光说不做可没有用

它的工作原理是每次检查相邻两个元素,如果前面的元素与后面的元素满足给定的排序条件,就将相邻两个元素交换。当没有相邻的元素需要交换时,排序就完成了。

显然,每一轮排序都会把最小(大)值放在数组的最前(后)面,所以 $ n - 1 $ 轮排序后就变成了一个有序的序列了

伪代码如下:

很完美是吧,就像图中的一样。

https://cdn.jsdelivr.net/gh/LogicShao/PicBed/img/bubbleSort.gif

但是,我们其实会发现这样的效率其实比较低。为什么呢?

在最坏的情况,冒泡排序需要 $ O(n^{2}) $ 次交换。冒泡排序的实现通常会对已经排序好的数列拙劣地执行 $ O(n^{2}) $ 次交换。

冒泡排序如果能在内部循环第一次执行时,使用一个旗标来表示有无需要交换的可能,就可以把最优情况下的复杂度降低到 $ O(n) $。在这个情况,已经排序好的数列就无交换的需要。若在每次走访数列时,把走访顺序反过来,也可以稍微地改进效率。有时候称为鸡尾酒排序,因为算法会从数列的一端到另一端之间穿梭往返。

$ AC\ code $

c艹

偶然间看见自己在高一时写的冒泡排序,还记得那时还是 $ WJM $ 学长教我算法呢

PY

赞赏
本文作者: Logic
本文链接: https://i.needwe.top/a-brief-discussion-on-sorting/
本文采用 CC BY-NC-SA 4.0 Unported 协议进行许可

发表回复

textsms
account_circle
email

  • 良君

    先生为之甚也,使我甚叹

    3年前 回复

Logic's Blog

【随笔】浅谈冒泡排序
一 公历十一月二十五日,也就是我发觉OJ上更了一道冒泡排序的那一天,我只在机房里探寻py之法,遇见泳良君,前来问我道:“可曾A了首题否?”我后悔万分,小声说道:“没有”。他就正告我其 $…
扫描二维码继续阅读
2021-11-27