冒泡排序為什麼會被看做經典，寫入所有C語言的教科書？

01-04

冒泡排序作為一種漸進複雜度O(N^2)的排序方法，實質上屬於一種形式「玄妙的」選擇排序，只是相比選擇排序多了一些無意義的交換。它比選擇排序更難於理解和解釋（就在於它多次無意義的交換的干擾，不信你講給樓下阿姨比較下），又不具有插入排序的「在線」優點，跟極易理解的基數排序更不能在思維難度上相比，就算同快排，歸併相比，也具有複雜度高得多的劣勢。那麼為什麼冒泡排序會作為經典，成為初學者學習語言的遇到的首個演算法？

其實呢只是為了講解怎麼用for循環

Bubble sort, the algorithm we should stop teaching

Bubble Sort: An Archaeological Algorithmic Analysis

What』s really so bad about bubble sort?

冒泡排序並不是一種有工程意義的排序演算法。不如說std::sort以外的也許都沒有工程意義……

但是講冒泡排序可以帶出幾個問題：

冒泡排序只有一個基本操作就是比較和交換相鄰的兩個元素，可以體現將一個複雜的問題轉化為非常簡單的操作的疊加的思想
冒泡排序看上去每一次循環都差不多，為什麼可以在有限次循環之內結束，如何分析演算法的正確性，這是一個不錯的數學問題
分析複雜度簡單，一眼就看得出來是O(n^2)。代碼也的確是最短的。邊界條件很少。甚至於多循環幾遍問題也不大。
分析完冒泡排序會發現，其他O(n^2)的演算法的原理都跟冒泡排序有共通之處：用O(n)的時間排出一個元素。所以講其他O(n^2)排序就不用花太多時間解釋了。

嘛其實哪個都不是什麼關鍵問題，其實也許最大的原因是因為這麼講沒啥毛病，所以也沒必要改吧……對於初學者來說，寫一個冒泡排序寫對的概率其實要比其他O(n^2)的演算法高不少。

另外冒泡排序有個小優點是很容易展開成沒有循環的形式，而且代碼也不會太難看，比如說我現在固定要排的是四個數，就可以寫：

#define cs(a,b) (if(a&>b){int t; t = a; a = b; b = t;}) cs(a,b);cs(b,c);cs(c,d);cs(a,b);cs(b,c);cs(a,b);

用別的排序就不太可能了。雖然現在編譯器都可以自動循環展開了，但以前並不是這樣，而且這樣小清新的代碼多好啊

從各個方面來看，插入排序、選擇排序都跟冒泡排序差不多。

所以如果要問為什麼冒泡排序這麼流行，我覺得原因有兩個：

冒泡排序描述形象、好玩；
歷史的慣性。

在磁帶上完成in-place排序

其實插入排序才是人類最自然的排序方法。

我們打撲克時是怎麼排列手中的牌的呢？插入排序。

冒泡排序可以說是一個用來對比的最壞的基準吧。

那是因為譚浩強的書用冒泡舉了例子，譚浩強的書被用作教材更多，造成的錯覺吧……

在給沒有基礎和概念的人看時，他至少能理解大泡泡浮在上面這個事情

經典，簡單！就跟你不論學什麼語言都先寫hello world一個道理吧，我學apk的時候居然第一個也是讓寫hello world。。

我怎麼覺得很多排序演算法的思想都很簡單。

也許是由於冒泡的代碼相當無腦？

抖個機靈。

因為冒泡排序還有改進的地方，只要加上一個計數器，計算本次內循環中交換的次數，如果交換的次數為0，就可以提前結束。（這樣的是不是就會比選擇好一點，跟插入差不多了呢）

我覺得是這個原因，基礎的冒泡排序雖然簡單，但是很多人都不會想到這一步，但是如果在學習的時候想到了，簡直神清氣爽。

so happy

插入，選擇，快排都比冒泡易於理解，而且更優，教科上這麼安排是故意繞彎子。

這種把簡單東西複雜化，是很多教科書的弊病。

冒泡法思想簡單易於描述，

只是傻獃獃地每次從前走到後不斷比較交換就可以了。

對於初學者來說，

是學習使用數組極好的練習。（很多初學者在這裡都犯過數組越界和不會數數的毛病）

而且，據Knuth講，

在某些情況下其實冒泡法是不二的選擇。

(冒泡法的另一個用處是可以用來練習分析演算法的效率)

學演算法總要從簡單開始吧。一來就歸併排序、堆排序、拓撲排序，會弄出毛病來的。

選擇排序不是需要額外的變數嘛，還是冒泡排序更簡單更容易理解一點。沒上來就講猴子排序就不錯了。

因為演算法本身簡單，名字形象，而且初學者很容易自己想出這個排序方法。

其實斯坦福公開課Programming Abstraction講排序的時候就不講冒泡排序，只是提過它，表示沒什麼好學的。

MIT公開課演算法導論就更加不講了，即使是分析普通性能的排序也是選了插入排序。

即便是冒泡這種初級排序，除了基本實現外還有兩種優化實現，面試時候面試官最愛問的就是！

「嗯，你答的很好，你答的是正確的，能不能再優化一下」

呵呵

冒泡排序是典型的「暴力求解演算法」，該過程中會有很多不必要的重複步驟，導致效率極低。而高效率的演算法，其實就是從中剔除多餘步驟，一步步演變出來的。好的老師應該會通過講解簡單的冒泡排序引導學生去分析演算法中的不足，進而改進演算法。其實還是蠻重要的

為什麼我覺得冒泡排序挺好理解的啊……

它的每次交換都使這個序列更加有序，一直到不用交換就說明整個序列排序完成。

好吧，最重要的是寫起來最簡單……

很久很久以前，磁頭移動也很慢，這時候看看冒泡，居然只要移動相鄰的位置，太棒了。

對初學者來說，我覺得選擇排序是最直觀最容易理解的。冒泡不是那麼自然想到的。

可能是慣性，別人都這麼寫書，所以我也這麼寫書，不動腦筋，不去設身處地的為讀者著想。

最後，冒泡排序在排序界雖然是渣渣，但是，冒泡排序的思想我覺得很有價值，很多隨機化演算法的思路和冒泡是一個模子的。

另外，冒泡排序的交換並非題主所說的無意義。

因為有趣，可以調動你的積極性，如果一上來就是插入排序，希爾排序什麼的，你肯定望而止步了。

知所先後，則近道矣