# 練習 16：冒泡、快速和歸并排序 > 原文：[Exercise 16: Bubble, Quick, and Merge Sort](https://learncodethehardway.org/more-python-book/ex16.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 你現在將嘗試為你的`DoubleLinkedList`數據結構實現排序算法。對于這些描述，我將使用“數字列表”來表示隨機的事物列表。這可能是一堆撲克牌，一張紙上的數字，名稱列表或其他任何可以排序的東西。當你嘗試排序數字列表時，通常有三個備選方案： > 冒泡排序 > 如果你對排序一無所知，這是你最可能嘗試的方式。它僅僅涉及遍歷列表，并交換你找到的任何亂序偶對。你不斷遍歷列表，交換偶對，直到你沒有交換任何東西。很容易理解，但是特別慢。 > 歸并排序 > 這種排序算法將列表分成兩半，然后是四個部分，直到它不能再分割為止。然后，它將這些返回的東西合并，但是在合并它時，通過檢查每個部分的順序，以正確的順序進行操作。這是一個聰明的算法，在鏈表上工作得很好，但在固定大小的數組上并不是很好，因為你需要某種`Queue`來跟蹤部分。 > 快速排序 > 這類似于歸并排序，因為它是一種“分治”算法，但它的原理是交換分割點周圍的元素，而不是將列表拆分合并在一起。在最簡單的形式中，你可以選擇從下界到上界的范圍和分割點。然后，交換分割點上方的大于它的元素，和下方的小于它的它元素。然后你選擇一個新的下界，上界和分割點，它們在這個新的無序列表里面，再執行一次。它將列表分成更小的塊，但它不會像歸并排序一樣拆分它們。 ## 挑戰練習 本練習的目的是，學習如何基于“偽代碼”描述或“p-code”的實現算法。你將使用我告訴你的參考文獻（主要是維基百科）研究算法，然后使用偽代碼實現它們。在這個練習的視頻中，我會在這里快速完成前兩個，更細節的東西留作練習。那么你的工作就是自己實現快速排序算法。首先，我們查看維基百科中[冒泡排序](https://en.wikipedia.org/wiki/Bubble_sort)的描述，來開始： ``` procedure bubbleSort( A : list of sortable items ) n = length(A) repeat swapped = false for i = 1 to n-1 inclusive do /* 如果這個偶對是亂序的 */ if A[i-1] > A[i] then /* 交換它們并且記住 */ swap( A[i-1], A[i] ) swapped = true end if end for until not swapped end procedure ``` 你會發現，因為偽代碼只是對算法的松散描述，它最終在不同書籍，作者和維基百科的頁面之間截然不同。它假設你可以閱讀這種“類編程語言”，并將其翻譯成你想要的內容。有時這種語言看起來像是一種叫做 Algol 的舊語言，其他的時候它會像格式不正確的 JavaScript 或者 Python 一樣。你只需要嘗試猜測它的意思，然后將其翻譯成你需要的。這是我對這個特定的偽代碼的最初實現： ```py def bubble_sort(numbers): """Sorts a list of numbers using bubble sort.""" while True: # 最開始假設它是有序的 is_sorted = True # 一次比較兩個，跳過頭部 node = numbers.begin.next while node: # 遍歷并將當前節點與上一個比較 if node.prev.value > node.value: # 如果上一個更大，我們需要交換 node.prev.value, node.value = node.value, node.prev.value # 這表示我們需要再次掃描 is_sorted = False node = node.next # 它在頂部重置過，但是如果我們沒有交換，那么它是有序的 if is_sorted: break ``` 我在這里添加了其他注釋，以便你可以學習并跟蹤它，將我在此處完成的內容與偽代碼進行比較。你還應該看到，維基百科頁面正在使用的數據結構，與`DoubleLinkedList`完全不同。維基百科的代碼假設在數組或列表結構上實現函數。你必須將下面這行： ``` if A[i-1] > A[i] then ``` 使用`DoubleLinkedList`翻譯為 Python： ```py if node.prev.value > node.value: ``` 我們不能輕易地隨機訪問`DoubleLinkedList`，所以我們必須將這些數組索引操作轉換為`.next`和`.prev`。在循環中，我們還必須注意`next`或`prev`屬性是否是`None`。這種轉換需要大量的翻譯，學習和猜測你正在閱讀的偽代碼的語義。 ### 學習冒泡排序 你現在應該花時間研究這個`bubble_sort`Python 代碼，看看我如何翻譯它。確保觀看我實時的視頻，并獲得更多的透視。你還應該繪制在不同類型的列表（已排序，隨機，重復等）上運行的圖表。一旦你了解我是如何做到的，為此研究`pytest`和`merge_sort`算法： ```py import sorting from dllist import DoubleLinkedList from random import randint max_numbers = 30 def random_list(count): numbers = DoubleLinkedList() for i in range(count, 0, -1): numbers.shift(randint(0, 10000)) return numbers def is_sorted(numbers): node = numbers.begin while node and node.next: if node.value > node.next.value: return False else: node = node.next return True def test_bubble_sort(): numbers = random_list(max_numbers) sorting.bubble_sort(numbers) assert is_sorted(numbers) def test_merge_sort(): numbers = random_list(max_numbers) sorting.merge_sort(numbers) assert is_sorted(numbers) ``` 這個測試代碼的一個重要部分是，我正在使用`random.randint`函數生成隨機數據進行測試。這個測試不會測試許多邊界情況，但這是一個開始，我們將在以后進行改進。記住，你沒有實現`sort.merge_sort`，所以你可以不寫這個測試函數，或者現在注釋它。 一旦你進行了測試，并且寫完了這個代碼，再次研究維基百科頁面，然后在嘗試`merge_sort`之前，嘗試一些其他的`bubble_sort`版本。 ### 歸并排序 我還沒準備好讓你自己實現它。我將再次對`merge_sort`函數重復此過程，但是這次我想讓你嘗試，從歸并排序的維基百科頁面 上的偽代碼中實現該算法，然后再查看我怎么做。有幾個建議的實現，但我使用“自頂向下”的版本： ```py function merge_sort(list m) if length of m ≤ 1 then return m var left := empty list var right := empty list for each x with index i in m do if i < (length of m)/2 then add x to left else add x to right left := merge_sort(left) right := merge_sort(right) return merge(left, right) function merge(left, right) var result := empty list while left is not empty and right is not empty do if first(left) ≤ first(right) then append first(left) to result left := rest(left) else append first(right) to result right := rest(right) while left is not empty do append first(left) to result left := rest(left) while right is not empty do append first(right) to result right := rest(right) return result ``` 為`test_merge_sort`編寫剩余測試用例函數，然后在這個實現上進行嘗試。我會給你一個線索，當僅僅使用第一個`DoubleLinkedListNode`時，該算法效果最好。你也可能需要一種方法，從給定的節點計算節點數。這是`DoubleLinkedList`不能做的事情。 ### 歸并排序作弊模式 如果你嘗試了一段時間并且需要作弊，這是我所做的： ```py def count(node): count = 0 while node: node = node.next count += 1 return count def merge_sort(numbers): numbers.begin = merge_node(numbers.begin) # horrible way to get the end node = numbers.begin while node.next: node = node.next numbers.end = node def merge_node(start): """Sorts a list of numbers using merge sort.""" if start.next == None: return start mid = count(start) // 2 # scan to the middle scanner = start for i in range(0, mid-1): scanner = scanner.next # set mid node right after the scan point mid_node = scanner.next # break at the mid point scanner.next = None mid_node.prev = None merged_left = merge_node(start) merged_right = merge_node(mid_node) return merge(merged_left, merged_right) def merge(left, right): """Performs the merge of two lists.""" result = None if left == None: return right if right == None: return left if left.value > right.value: result = right result.next = merge(left, right.next) else: result = left result.next = merge(left.next, right) result.next.prev = result return result ``` 在嘗試實現它時，我將使用此代碼作為“備忘單”來快速獲取線索。你還會看到，我在視頻中嘗試從頭開始重新實現此代碼，因此你可以看到我努力解決你可能遇到過的相同問題。 ### 快速排序 最后，輪到你嘗試實現`quick_sort`并創建`test_quicksort`測試用例。我建議你首先使用 Python 的普通列表類型實現簡單的快速排序。這將有助于你更好地理解它。然后，使用簡單的 Python 代碼，并使其處理`DoubleLinkedList`（的頭節點）。記住要把你的時間花費在這里，顯然還要在你的`test_quicksort`里進行大量的調試和測試。 ## 深入學習 + 這些實現在性能上絕對不是最好的。嘗試寫一些喪心病狂的測試來證明這一點。你可能需要將一個很大的列表傳給算法。使用你的研究來找出病態（絕對最差）的情況。例如，當你把一個有序的列表給`quick_sort`時會發生什么？ + 不要實現任何改進，但研究你可以對這些算法執行的，各種改進方法。 + 查找其他排序算法并嘗試實現它們。 + 它們還可以在`SingleLinkedList`上工作嗎？`Queue`和`Stack`呢？它們很實用嗎？ + 了解這些算法的理論速度。你會看到`O(n^2)`或`O(nlogn)`的引用，這是一種說法，在最壞的情況下，這些算法的性能很差。為算法確定“大O”超出了本書的范圍，但我們將在練習 18 中簡要討論這些度量。 + 我將這些實現為一個單獨的模塊，但是將它們作為函數，添加到`DoubleLinkedList`更簡單嗎？如果你這樣做，那么你需要將該代碼復制到可以處理的其他數據結構上嗎？我們沒有這樣的設計方案，如何使這些排序算法處理任何“類似鏈表的數據結構”。 + 再也不要使用氣泡排序。我把它包含在這里，因為你經常遇到壞的代碼，并且我們會在練習 19 中提高其性能。