浙江大學-數據結構-簡單排序-9.1.2

上一節我們講了一下在本課中排序演算法的一些前提，那我們先從最簡單的冒泡排序開始講起，那冒泡排序這個名字看是一個非常形象的名字，假設我們有這麼一堆的泡泡，我們的目標是要把最小的泡泡排在最上面，最大的泡泡排在下面，那麼它是怎麼做的呢？它每次從上到下，比較兩個相鄰的泡泡，如果它們的順序是對的，也就是如果小的在上面，大的在下面，那就不動了，如果順序是錯的，就要把順序換一下，在一趟排序完成之後，我們看到不管前面這些泡泡的狀況是什麼樣子的，有一件事情是可以肯定的，最大的泡泡一定已經放到了最下面，那麼最大的泡泡，它的位置就已經確認了，那麼接下去呢，我們在做第二趟排序的時候，仍然從上到下，重複這個過程，但是我們只需要對前面的，n-1個數重複這個過程就好了，重複完了以後，再對n-2個數進行重複，這就是一個非常簡單的冒泡排序，這是一個冒泡排序的偽碼描述

這是一個冒泡排序的偽碼描述，它是叫Bubble_Sort,叫冒泡排序，這裡頭描述的是一趟冒泡所做的事情，我們每次從i=0開始，從最上面開始，然後比較相鄰的A[i]和A[i+1],相鄰的兩個元素的大小，如果上面的比下面的大的話，我們需要swap交換這兩個元素的位置，一直執行到什麼時候呢，這個P指的是最後一個元素的位置，當i等於P-1的時候，把P和P-1比較一下，做最後一次交換，那麼這就完成了一趟冒泡，在第一次開始的時候，這個P應該是等於多少呢？最後一個元素的位置應該是n-1,對不對？接著下一趟冒泡的時候，這個P就要減小了，就會指在這個位置，

就是滑鼠指的位置，就是P-2,外面這個循環是關於P的循環，它是從N-1開始，每一次減小一個單元，也就是說每次這個位置向上挪一個單位，一直到P==0的時候，我們就完成了整個的冒泡排序，這個看上去非常簡單，但是中間有一個問題你有沒有發現，如果我們運氣比較好，在中間某一步的時候，它就已經有序了，那這個程序知道不知道呢，這個程序是不知道的，它會閉著眼睛去做完兩重循環，不管是不是做交換，但是它每次必須要去比較一下，那這個事情就有點傻，要怎麼改呢？什麼情況下，我就知道它已經有序了，不需要再往下做了呢？那就是當我一趟排序從頭走到尾，都發現沒有任何一對元素需要交換位置的時候，也就是說如果這個Swap在這一趟排序裡面，從來沒有被執行過，那麼我們就知道這個序列一定是完全有序的，就不用往下做了，那麼我們怎麼知道這一點呢？很簡單，我加一個標記，叫做flag,flag一開始的時候等於0，表示我還沒有執行過任何一次的交換，當我要做交換的時候，那麼我就把這個flag設成1，它來標識說我們曾經在這一趟排序裡面發生過了交換，

那麼等我這一趟排序排完了以後，出來的時候，我在這判斷一下，如果這個flag,從來沒有被改變過，一直都是0的話，那麼說明全程無交換，整個序列已經有序了，我們就可以break,跳出來了，

那我們看一下這個冒泡排序的時間複雜度，它有兩種情況，一種是最好的情況，一種是最壞的情況，最好的情況就是一開始這些泡泡都是排好序的，從始至終，我都不需要執行任何一次的交換，但是呢，無論如何，我得從上到下掃描一遍，所以我們的最好情況是說，一開始它已經是它已經是順序的，那我只需要從頭到尾掃描一遍整個的序列，用一個O(N)的時間，我就可以從這裡break,跳出這個循環了，最壞情況是什麼樣的呢？整個是逆序的，一開始的時候，最大的泡泡在最上面，最小的泡泡在最下面，於是呢，每一趟排序我們都只能把最大的泡泡挪到下面來，然後下一趟排序，次大的泡泡挪到下面來，我們必須要走滿這n-1趟排序，然後每一趟排序，兩兩元素要不停的做交換，所以最壞情況下是逆序，時間複雜度是O(N^2),冒泡排序的好處是什麼，非常簡單，這個程序，如果你要不加這個標識的話，就是兩重for循環加一層if判斷，相當簡單，當然了，它的表現就不是很好，一個O(N^2)數量級的排序演算法往往是不可接受的，但是為什麼說冒泡排序也有它的好處呢？它有一個好處是別的排序演算法比不了的，我們在這雖然寫的好像是說所有的待排元素都放到一個數組裡，但是如果有一種情況比較變態，所有的待排元素是放在一個單向鏈表裡的，那個時候你要怎麼做呢？等你學了更多的排序演算法以後，你可以回過頭來想一想冒泡排序是沒問題的，它每次是從上到下往一個方向掃描，而且每次交換相鄰的兩個元素，這個對於數組沒有問題，對於鏈表呢，也沒有問題，但是其它的排序演算法呢，好像就不容易做到這一點，那另外，冒泡排序還有一個好處，就是你要注意到，我們什麼時候做交換呢，只有當這個元素嚴格大於下一個元素的時候，我們才做交換，如果它們兩個是相等的話，我們是不做交換的，這點內就保證了，我們這個排序演算法它是穩定的。