練習(xí) 16：冒泡、快速和歸并排序
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0
自豪地采用谷歌翻譯
你現(xiàn)在將嘗試為你的DoubleLinkedList數(shù)據(jù)結(jié)構(gòu)實現(xiàn)排序算法。對于這些描述，我將使用“數(shù)字列表”來表示隨機的事物列表。這可能是一堆撲克牌，一張紙上的數(shù)字，名稱列表或其他任何可以排序的東西。當(dāng)你嘗試排序數(shù)字列表時，通常有三個備選方案：
冒泡排序
如果你對排序一無所知，這是你最可能嘗試的方式。它僅僅涉及遍歷列表，并交換你找到的任何亂序偶對。你不斷遍歷列表，交換偶對，直到你沒有交換任何東西。很容易理解，但是特別慢。
歸并排序
這種排序算法將列表分成兩半，然后是四個部分，直到它不能再分割為止。然后，它將這些返回的東西合并，但是在合并它時，通過檢查每個部分的順序，以正確的順序進行操作。這是一個聰明的算法，在鏈表上工作得很好，但在固定大小的數(shù)組上并不是很好，因為你需要某種
Queue來跟蹤部分。
快速排序
這類似于歸并排序，因為它是一種“分治”算法，但它的原理是交換分割點周圍的元素，而不是將列表拆分合并在一起。在最簡單的形式中，你可以選擇從下界到上界的范圍和分割點。然后，交換分割點上方的大于它的元素，和下方的小于它的它元素。然后你選擇一個新的下界，上界和分割點，它們在這個新的無序列表里面，再執(zhí)行一次。它將列表分成更小的塊，但它不會像歸并排序一樣拆分它們。
挑戰(zhàn)練習(xí)
本練習(xí)的目的是，學(xué)習(xí)如何基于“偽代碼”描述或“p-code”的實現(xiàn)算法。你將使用我告訴你的參考文獻（主要是維基百科）研究算法，然后使用偽代碼實現(xiàn)它們。在這個練習(xí)的視頻中，我會在這里快速完成前兩個，更細節(jié)的東西留作練習(xí)。那么你的工作就是自己實現(xiàn)快速排序算法。首先，我們查看維基百科中冒泡排序的描述，來開始：
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
你會發(fā)現(xiàn)，因為偽代碼只是對算法的松散描述，它最終在不同書籍，作者和維基百科的頁面之間截然不同。它假設(shè)你可以閱讀這種“類編程語言”，并將其翻譯成你想要的內(nèi)容。有時這種語言看起來像是一種叫做 Algol 的舊語言，其他的時候它會像格式不正確的 JavaScript 或者 Python 一樣。你只需要嘗試猜測它的意思，然后將其翻譯成你需要的。這是我對這個特定的偽代碼的最初實現(xiàn)：
def bubble_sort(numbers):
"""Sorts a list of numbers using bubble sort."""
while True:
# 最開始假設(shè)它是有序的
is_sorted = True
# 一次比較兩個，跳過頭部
node = numbers.begin.next
while node:
# 遍歷并將當(dāng)前節(jié)點與上一個比較
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
我在這里添加了其他注釋，以便你可以學(xué)習(xí)并跟蹤它，將我在此處完成的內(nèi)容與偽代碼進行比較。你還應(yīng)該看到，維基百科頁面正在使用的數(shù)據(jù)結(jié)構(gòu)，與DoubleLinkedList完全不同。維基百科的代碼假設(shè)在數(shù)組或列表結(jié)構(gòu)上實現(xiàn)函數(shù)。你必須將下面這行：
if A[i-1] > A[i] then
使用DoubleLinkedList翻譯為 Python：
if node.prev.value > node.value:
我們不能輕易地隨機訪問DoubleLinkedList，所以我們必須將這些數(shù)組索引操作轉(zhuǎn)換為.next和.prev。在循環(huán)中，我們還必須注意next或prev屬性是否是None。這種轉(zhuǎn)換需要大量的翻譯，學(xué)習(xí)和猜測你正在閱讀的偽代碼的語義。
學(xué)習(xí)冒泡排序
你現(xiàn)在應(yīng)該花時間研究這個bubble_sortPython 代碼，看看我如何翻譯它。確保觀看我實時的視頻，并獲得更多的透視。你還應(yīng)該繪制在不同類型的列表（已排序，隨機，重復(fù)等）上運行的圖表。一旦你了解我是如何做到的，為此研究pytest和merge_sort算法：
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函數(shù)生成隨機數(shù)據(jù)進行測試。這個測試不會測試許多邊界情況，但這是一個開始，我們將在以后進行改進。記住，你沒有實現(xiàn)sort.merge_sort，所以你可以不寫這個測試函數(shù)，或者現(xiàn)在注釋它。
一旦你進行了測試，并且寫完了這個代碼，再次研究維基百科頁面，然后在嘗試merge_sort之前，嘗試一些其他的bubble_sort版本。
歸并排序
我還沒準備好讓你自己實現(xiàn)它。我將再次對merge_sort函數(shù)重復(fù)此過程，但是這次我想讓你嘗試，從歸并排序的維基百科頁面 上的偽代碼中實現(xiàn)該算法，然后再查看我怎么做。有幾個建議的實現(xiàn)，但我使用“自頂向下”的版本：
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編寫剩余測試用例函數(shù)，然后在這個實現(xiàn)上進行嘗試。我會給你一個線索，當(dāng)僅僅使用第一個DoubleLinkedListNode時，該算法效果最好。你也可能需要一種方法，從給定的節(jié)點計算節(jié)點數(shù)。這是DoubleLinkedList不能做的事情。
歸并排序作弊模式
如果你嘗試了一段時間并且需要作弊，這是我所做的：
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
在嘗試實現(xiàn)它時，我將使用此代碼作為“備忘單”來快速獲取線索。你還會看到，我在視頻中嘗試從頭開始重新實現(xiàn)此代碼，因此你可以看到我努力解決你可能遇到過的相同問題。
快速排序
最后，輪到你嘗試實現(xiàn)quick_sort并創(chuàng)建test_quicksort測試用例。我建議你首先使用 Python 的普通列表類型實現(xiàn)簡單的快速排序。這將有助于你更好地理解它。然后，使用簡單的 Python 代碼，并使其處理DoubleLinkedList（的頭節(jié)點）。記住要把你的時間花費在這里，顯然還要在你的test_quicksort里進行大量的調(diào)試和測試。
深入學(xué)習(xí)
- 這些實現(xiàn)在性能上絕對不是最好的。嘗試寫一些喪心病狂的測試來證明這一點。你可能需要將一個很大的列表傳給算法。使用你的研究來找出病態(tài)（絕對最差）的情況。例如，當(dāng)你把一個有序的列表給
quick_sort時會發(fā)生什么？ - 不要實現(xiàn)任何改進，但研究你可以對這些算法執(zhí)行的，各種改進方法。
- 查找其他排序算法并嘗試實現(xiàn)它們。
- 它們還可以在
SingleLinkedList上工作嗎？Queue和Stack呢？它們很實用嗎？ - 了解這些算法的理論速度。你會看到
O(n^2)或O(nlogn)的引用，這是一種說法，在最壞的情況下，這些算法的性能很差。為算法確定“大O”超出了本書的范圍，但我們將在練習(xí) 18 中簡要討論這些度量。 - 我將這些實現(xiàn)為一個單獨的模塊，但是將它們作為函數(shù)，添加到
DoubleLinkedList更簡單嗎？如果你這樣做，那么你需要將該代碼復(fù)制到可以處理的其他數(shù)據(jù)結(jié)構(gòu)上嗎？我們沒有這樣的設(shè)計方案，如何使這些排序算法處理任何“類似鏈表的數(shù)據(jù)結(jié)構(gòu)”。 - 再也不要使用氣泡排序。我把它包含在這里，因為你經(jīng)常遇到壞的代碼，并且我們會在練習(xí) 19 中提高其性能。
