比冒泡演算法還簡單的排序演算法:看起來滿是bug的程式,居然是對的

来源:https://www.cnblogs.com/javastack/archive/2022/08/01/16540960.html
-Advertisement-
Play Games

明敏 曉查 發自 凹非寺 量子位 報道 | 公眾號 QbitAI 程式 bug 也能負負得正嗎? 還真可以。 比如程式員們再熟悉不過的排序演算法,通過兩個“bug”居然能歪打正著,實在令人匪夷所思。 請看這位程式員寫的數組升序排序代碼: for i = 1 to n do for j = 1 to n ...


明敏 曉查 發自 凹非寺
量子位 報道 | 公眾號 QbitAI

程式 bug 也能負負得正嗎?

還真可以。

比如程式員們再熟悉不過的排序演算法,通過兩個“bug”居然能歪打正著,實在令人匪夷所思。

請看這位程式員寫的數組升序排序代碼:

for i = 1 to n do
  for j = 1 to n do
    if A[i] < A[j] then
      swap A[i] and A[j]

最近這串代碼在 Hacker News 論壇上突然火了起來,引來大批程式員圍觀。

乍一看這段代碼,你的反應會是什麼?會不會覺得這個程式員水平太差了,連基本的冒泡演算法都寫不好:

不等號方向錯了,第二層迴圈指數 j 的範圍也弄錯了。

總之,這段代碼“絕對不可能正確”。

冒泡演算法

但如果你真的運行一下會發現,結果還真的是按照升序排列的。

我們再來看一下正確的冒泡演算法代碼是怎樣的:

for i = 1 to n do
  for j = i + 1 to n do
    if A[i] > A[j] then
      swap A[i] and A[j]

後者不同之處是 j = i + 1A[i] > A[j],兩段程式大相徑庭。

然而我要告訴你一個不可思議的事實,其實第一串代碼是對的,而且可以嚴格證明。

那麼它是如何實現正確排序的?

為何能歪打正著

仔細一想,其實很容易理解。因為該演算法比冒泡排序多一半交換操作,正好可以將降序編程升序。

不過,作者還是給出了嚴格的證明。

我們定義 Pᵢ 是經過 i 次(1 ≤ i ≤ n)外迴圈後得到的數組。

如果演算法正確,那麼前 i 項已經是升序排列,即 A[1] ≤ A[2] ≤ . . . ≤ A[i]。

證明該演算法正確,實際上就是證明 Pₙ 對於任何 n 都成立。

根據數學歸納法,我們只要證明 P₁ 成立,假設 Pᵢ 成立,接著再證明 Pi+1 也成立,命題即可得證。

P₁ 顯然是正確的,而且這一步和普通的冒泡演算法降序沒有區別,經過第 1 次外迴圈,A[1] 就是整個數組的最大元素。

接著我們假設 Pᵢ 成立,然後證明 Pi+1 成立。

我們先定義一個序數 k:

首先假設 A[k](k 介於 1~i 之間)滿足 A[k]>A[i+1] 最小的一個數,那麼 A[k−1]≤A[i+1](k≠1)。

如果 A[i+1]≥A[i],那麼這樣的 k 不存在,我們就令 k=i+1。

考慮以下三種情況:

1、1 ≤ j ≤ k−1

由於 A[i+1]>A[j],沒有任何元素交換髮生。

2、 k ≤ j ≤ i (如果 k=i+1,則不存在此步驟)

由於 A[j]>A[i+1],所以每次比較後都會有元素交換髮生。

我們使用 A[ ] 和 A′[ ] 來表示交換前和交換後的元素,所以

A′[i+1] = A[k],A′[k]=A[i+1]

經過一系列交換,最大元素最終被放到了 A[i+1] 位置上,原來的 A[i+1] 變成了最大元素,A[k] 被插入了大小介於原來 A[k] 和 A[k-1] 之間的元素。

3、i+1 ≤ j ≤ n

由於最大元素已經交換到前 i+1 個元素中,此過程也沒有任何元素交換。

最後,Pₙ 就是升序排序演算法執行完以後的結果。

由於內外兩組迴圈沒有任何範圍差別,因此這可以說是“最簡單”的排序演算法了。

從代碼上來看,它很像冒泡演算法,但從證明過程中可以看出,這實際上是一種插入演算法

插入演算法

演算法複雜度

顯然,該演算法總會進行 n² 次比較,接下來計算演算法的交換次數。

可以證明交換其次最多為 I+2(n-1),最少為 n-1。

其中 I 為初始數字的逆序數,最大為 n(n-1)/2

因此整個演算法的複雜度為 O(n²)。

從證明過程中可以看出,除了 i=1 的迴圈以外,其餘迴圈里 j=i-1 之後的部分完全無效,因此可以將這部分省略,得到簡化後的演算法。

for i = 2 to n do
  for j = 1 to i − 1 do
    if A[i] < A[j] then
      swap A[i] and A[j]

該演算法減少了比較和交換次數,不過演算法複雜度依然是 O(n²)。

網友:這個演算法我以前見過

比最容易理解的冒泡演算法還要簡單,這個排序演算法在 Hacker News 上很快引起了網友的圍觀。

不少人覺得它“很眼熟”。

有位網友表示,自己曾在奧林匹克數學競賽中看到一個同學用了一種非常奇怪的排序演算法,它可以運行但是效率很低,更像是一種插入排序。

如果我沒記錯的話,他用的就是這種演算法。

事實上,關於這種演算法的討論已久,從 2014 年開始就不斷有人發帖,這次作者將論文上傳到 arXiv 後又引起了廣泛熱議。

甚至還有烏龍事件發生。

有位網友掃了一眼論文就以為這個演算法和自己 10 年前提出的一樣。

留言網友的演算法:

乍一看兩種演算法的代碼確實很像,原理上的確有些相似。

都是看起來像冒泡排序,但其實更貼近選擇排序。

不過很快有人指出真相:這種演算法中 j=i+1 to n,並且是當 A[i] > A[j] 時交換。

而作者提出的演算法中 j=1 to n,A[i] < A[j] 時交換。

兩種演算法相比,網友此前提出的更容易被理解為什麼可以運行。

當然也有歪樓的,有人就調侃自己剛學編程時寫過這個演算法。

我百分百確定,在我剛開始學編程、並想要找到最短的排序方法時就寫過它。

不過說到實際應用上,這種演算法需要的計算時間太長了。

有人就認為,這種演算法此前被髮現過很多次,但是那些人根本沒打算用它。

也有人提出:這種排序沒有睡眠排序簡單。

睡眠排序就是構造 n 個線程,讓線程和排序的 n 個數對應。

例如對於 [4,2,3,5,9] 這樣一組數字,就創建 5 個線程,每個線程睡眠 4s,2s,3s,5s,9s。這些線程睡醒之後,就把自己對應的數報出來即可。這樣等所有線程都醒來,排序就結束了。

但和作者提出的演算法一樣,睡眠排序由於多線程的問題,在真正實現上也有困難

此外,這位網友也表示自己看到過這種演算法:

我確定我此前看到過這種演算法,它沒有名字嗎?

很快就有人提議說——

如果它沒有名字的話,我建議稱之為“面試排序”。

近期熱文推薦:

1.1,000+ 道 Java面試題及答案整理(2022最新版)

2.勁爆!Java 協程要來了。。。

3.Spring Boot 2.x 教程,太全了!

4.別再寫滿屏的爆爆爆炸類了,試試裝飾器模式,這才是優雅的方式!!

5.《Java開發手冊(嵩山版)》最新發佈,速速下載!

覺得不錯,別忘了隨手點贊+轉發哦!


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 精華筆記: 1. 迴圈結構: - for結構:應用率高、與次數相關的迴圈 ```java 1)語法: // 1 2 3 for(要素1;要素2;要素3){ 語句塊/迴圈體 反覆執行的語句 4 } 2)執行過程: 1243243243243243...2 ``` 2. 三種迴圈結構如何選擇: - 先看 ...
  • 前言 大晚上的,老是刷到有關pprof的文章,忍不住看了幾篇文章...寫個學習筆記記錄下~ 正文: 1.pprof是什麼? pprof是go內置的性能調優工具,可以藉助一些工具以圖形化的方式展示出來某些介面占用cpu資源的詳情。 2.專項用途: 1.cpu 主要測試占用cpu資源比較多的函數或者數據 ...
  • 一 、with語句的原理 上下文管理協議(Context Management Protocol):包含方法 __enter__()和__exit__(),支持該協議的對象要實現這兩個方法。 上下文管理器(Context Manager):支持上下文管理協議的對象,這種對象實現了__enter__( ...
  • 前言: 今天用for range寫了個demo,發現無論怎麼運行,最後的結果是一直是最後一個。自己思考過後,又和其他伙伴商量了下,最終算是解決了自己的疑惑。 正文: 下麵我們來看個例子: m := make(map[int]*int) arr := []int{1, 2, 3, 4, 5} for ...
  • 簡單記錄,分享下這段時間學習Flask所用過的資料 學習Flask的這段時間,我在網上找了挺多,也看了挺多的資料,有視頻,也有文檔教程。 然後我發現,這方面資料有點雜而不全,就沒有特別好的的教程可看,而且對於咱這樣的新手如果一開始就去看官方的文檔,也看的迷迷糊糊,最後發現還是什麼都不會。 經過我這段 ...
  • 兄弟們,今天來實現一下用Python編寫密碼檢測器,並輸出詳細信息! 本次涉及知識點 文件讀寫 基礎語法 字元串處理 迴圈遍歷 代碼展示 # 導入系統包 import platform # 我給大家準備了一些資料,包括2022最新Python視頻教程、Python電子書10個G (涵蓋基礎、爬蟲、數 ...
  • 面向對象03 10.抽象類 abstract修飾符可以用來修飾方法也可以修飾類,如果修飾方法,那麼該方法就是抽象方法;如果修飾類,那麼該類就是抽象類 抽象類中可以沒有抽象方法,但是有抽象方法的類一定要聲明為抽象類 抽象類,不能使用new關鍵字來創建對象,它是用來讓子類繼承的 抽象方法,只有方法的聲明 ...
  • indexOf和subString取值走向圖;首先簡單介紹這者的作用,具體可以看官方API 1.indexOf的作用: 就是獲取某個字元串的其中具體一個字元的位置 2.subString的作用: 就是大家熟悉的切割,從那裡到那裡比如,從第一個到第五個等;當這個方法是重載的,不只有我說的這個方法;具體 ...
一周排行
    -Advertisement-
    Play Games
  • 經常看到有群友調侃“為什麼搞Java的總在學習JVM調優?那是因為Java爛!我們.NET就不需要搞這些!”真的是這樣嗎?今天我就用一個案例來分析一下。 昨天,一位學生問了我一個問題:他建了一個預設的ASP.NET Core Web API的項目,也就是那個WeatherForecast的預設項目模 ...
  • 很多軟體工程師都認為MD5是一種加密演算法,然而這種觀點是不對的。作為一個 1992 年第一次被公開的演算法,到今天為止已經被髮現了一些致命的漏洞。本文討論MD5在密碼保存方面的一些問題。 ...
  • Maven可以使我們在構建項目時需要用到很多第三方類jar包,如下一些常用jar包 而maven的出現可以讓我們避免手動導入jar包出現的某些問題,它可以自動下載那須所需要的jar包 我們只需要在創建的maven項目自動生成的pom.xml中輸入如下代碼 <dependencies> <!--ser ...
  • 來源:https://developer.aliyun.com/article/694020 非同步調用幾乎是處理高併發Web應用性能問題的萬金油,那麼什麼是“非同步調用”? “非同步調用”對應的是“同步調用”,同步調用指程式按照定義順序依次執行,每一行程式都必須等待上一行程式執行完成之後才能執行;非同步調 ...
  • 1.面向對象 面向對象編程是在面向過程編程的基礎上發展來的,它比面向過程編程具有更強的靈活性和擴展性,所以可以先瞭解下什麼是面向過程編程: 面向過程編程的核心是過程,就是分析出實現需求所需要的步驟,通過函數一步一步實現這些步驟,接著依次調用即可,再簡單理解就是程式 從上到下一步步執行,從頭到尾的解決 ...
  • 10瓶毒藥其中只有一瓶有毒至少需要幾隻老鼠可以找到有毒的那瓶 身似浮雲,心如飛絮,氣若游絲。 用二分查找和二進位位運算的思想都可以把死亡的老鼠降到最低。 其中,二進位位運算就是每一隻老鼠代表一個二進位0或1,0就代表老鼠存活,1代表老鼠死亡;根據數學運算 23 = 8、24 = 16,那麼至少需要四 ...
  • 一、Kafka存在哪些方面的優勢 1. 多生產者 可以無縫地支持多個生產者,不管客戶端在使用單個主題還是多個主題。 2. 多消費者 支持多個消費者從一個單獨的消息流上讀取數據,而且消費者之間互不影響。 3. 基於磁碟的數據存儲 支持消費者非實時地讀取消息,由於消息被提交到磁碟,根據設置的規則進行保存 ...
  • 大家好,我是陶朱公Boy。 前言 上一篇文章《關於狀態機的技術選型,最後一個真心好》我跟大家聊了一下關於”狀態機“的話題。從眾多技術選型中我也推薦了一款阿裡開源的狀態機—“cola-statemachine”。 於是就有小伙伴私信我,自己項目也考慮引入這款狀態機,但網上資料實在太少,能不能系統的介紹 ...
  • 使用腳本自動跑實驗(Ubuntu),將實驗結果記錄在文件中,併在實驗結束之後將結果通過郵件發送到郵箱,最後在windows端自動解析成excel表格。 ...
  • 話說在前面,我不是小黑子~ 我是超級大黑子😏 表弟大周末的跑來我家,沒事幹天天騷擾我,搞得我都不能跟小姐姐好好聊天了,於是為了打發表弟,我決定用Python做一個小游戲來消耗一下他的精力,我思來想去,決定把他變成小黑子,於是做了一個坤坤打籃球的游戲,沒想到他還挺愛玩的~ 終於解放了,於是我把游戲寫 ...