排序算法之冒泡排序及其優化
- 2020 年 3 月 2 日
- 筆記
冒泡排序
思想
比較相鄰兩個元素，如果前面的元素比後面的元素大，則交換位置。最後一個元素必定會是最大值。
排除掉最後一位元素，繼續循環，直至沒有元素需要比較
可以看出，冒牌排序其實和選擇排序時很像的，只不過選擇排序是比較數據，先記錄下最小/大值的下標，等一趟循環結束的時候再交換位置；
而冒泡排序在比較數據的同時也做了交換。
性能
時間複雜度與選擇排序一樣，時間複雜度為O(n^2)。
由於它們的比較次數一樣，而冒泡排序的交換次數多，所以一般冒泡排序會比選擇排序慢。
但冒泡排序有一個優勢，那就是每經過一次循環，數組的有序性就會變高。我們可以利用這點來優化冒泡排序，優化方法請看下文。
代碼
普通冒泡排序的Python代碼：
# 冒泡排序 def bubbleSort(arr): size = len(arr) for i in range(size - 1, 0, -1): for j in range(i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j]優化
優化一
我們會發現如果數組一開始就是有序的或者再經過前幾次循環的時候就已經變得有序了，但上述程序還是會繼續循環比較。針對這一點我們可以進行一次優化：
# 冒泡排序（優化一） def bubbleSort(arr): size = len(arr) for i in range(size - 1, 0, -1): # 設一個flag，True表示沒有交換 hasNoChange = True for j in range(i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] # 交換數據，設為False hasNoChange = False # 如果沒有交換，證明數組已經有序了，可以結束循環 if hasNoChange: break經過優化之後，最好的情況下，時間複雜度為O(n)。
優化二
優化一針對的是整個數組已經有序的情況。那如果一個數組，假設有一萬個數據，其實從一開始或者幾次循環之後，後5千個數據已經是有序的且比前5千個數據要大，
在上述代碼中，每次循環仍然會循環到上次循環找出的最大值的前一位。針對這一點，我們還可以再做一次優化：
# 冒泡排序（優化二） def bubbleSort(arr): size = len(arr) # 最後一次交換的位置 lastChangedIdx = size - 1 for i in range(len(arr), 0, -1): tmpIdx = -1 # 只需要比較到上次交換的位置 for j in range(lastChangedIdx): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] tmpIdx = j # 如果沒有交換，證明數組已經有序了，可以結束循環 if tmpIdx == -1: break # 如果有交換，將最後一次交換的位置賦給lastChangedIdx else: lastChangedIdx = tmpIdx優化三
假如還是剛才那個數組，後五千個數據已經有序，但最後一位是整個數組中的最小值，我們會發現優化二中的優化根本起不了作用。
那想要讓優化二起作用，那麼就需要把那個最小值拿到前面來，有什麼辦法呢？很簡單，就是來一次反向冒泡就行了。
這樣的算法被叫做雙向冒泡排序（也叫雞尾酒排序），為了高雅地裝逼，我們就叫它雞尾酒排序吧。
# 冒泡排序（優化三，雞尾酒排序） def bubbleSort(arr): size = len(arr) # 正向最後一次交換的位置 rightLastChangedIdx = size - 1 # 反向最後一次交換的位置 leftLastChangedIdx = 0 for i in range(size >> 1): tmpIdx = -1 # 正向冒泡：從反向最後一次交換的位置到正向最後一次交換的位置 for j in range(leftLastChangedIdx, rightLastChangedIdx): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] tmpIdx = j # 如果沒有交換，證明數組已經有序了，可以結束循環 if tmpIdx == -1: break # 如果有交換，將最後一次交換的位置賦給rightLastChangedIdx else: rightLastChangedIdx = tmpIdx tmpIdx = -1 # 反向冒泡：從正向最後一次交換的位置到反向最後一次交換的位置 for k in range(rightLastChangedIdx, leftLastChangedIdx, -1): if arr[k] < arr[k - 1]: arr[k], arr[k - 1] = arr[k - 1], arr[k] tmpIdx = k # 如果沒有交換，證明數組已經有序了，可以結束循環 if tmpIdx == -1: break # 如果有交換，將最後一次交換的位置賦給leftLastChangedIdx else: leftLastChangedIdx = tmpIdx
