练习 16:冒泡、快速和归并排序

原文:Exercise 16: Bubble, Quick, and Merge Sort

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

你现在将尝试为你的DoubleLinkedList数据结构实现排序算法。对于这些描述,我将使用“数字列表”来表示随机的事物列表。这可能是一堆扑克牌,一张纸上的数字,名称列表或其他任何可以排序的东西。当你尝试排序数字列表时,通常有三个备选方案:

冒泡排序

如果你对排序一无所知,这是你最可能尝试的方式。它仅仅涉及遍历列表,并交换你找到的任何乱序偶对。你不断遍历列表,交换偶对,直到你没有交换任何东西。很容易理解,但是特别慢。

归并排序

这种排序算法将列表分成两半,然后是四个部分,直到它不能再分割为止。然后,它将这些返回的东西合并,但是在合并它时,通过检查每个部分的顺序,以正确的顺序进行操作。这是一个聪明的算法,在链表上工作得很好,但在固定大小的数组上并不是很好,因为你需要某种Queue来跟踪部分。

快速排序

这类似于归并排序,因为它是一种“分治”算法,但它的原理是交换分割点周围的元素,而不是将列表拆分合并在一起。在最简单的形式中,你可以选择从下界到上界的范围和分割点。然后,交换分割点上方的大于它的元素,和下方的小于它的它元素。然后你选择一个新的下界,上界和分割点,它们在这个新的无序列表里面,再执行一次。它将列表分成更小的块,但它不会像归并排序一样拆分它们。

挑战练习

本练习的目的是,学习如何基于“伪代码”描述或“p-code”的实现算法。你将使用我告诉你的参考文献(主要是维基百科)研究算法,然后使用伪代码实现它们。在这个练习的视频中,我会在这里快速完成前两个,更细节的东西留作练习。那么你的工作就是自己实现快速排序算法。首先,我们查看维基百科中冒泡排序的描述,来开始:

  1. procedure bubbleSort( A : list of sortable items )
  2. n = length(A)
  3. repeat
  4. swapped = false
  5. for i = 1 to n-1 inclusive do
  6. /* 如果这个偶对是乱序的 */
  7. if A[i-1] > A[i] then
  8. /* 交换它们并且记住 */
  9. swap( A[i-1], A[i] )
  10. swapped = true
  11. end if
  12. end for
  13. until not swapped
  14. end procedure

你会发现,因为伪代码只是对算法的松散描述,它最终在不同书籍,作者和维基百科的页面之间截然不同。它假设你可以阅读这种“类编程语言”,并将其翻译成你想要的内容。有时这种语言看起来像是一种叫做 Algol 的旧语言,其他的时候它会像格式不正确的 JavaScript 或者 Python 一样。你只需要尝试猜测它的意思,然后将其翻译成你需要的。这是我对这个特定的伪代码的最初实现:

  1. def bubble_sort(numbers):
  2. """Sorts a list of numbers using bubble sort."""
  3. while True:
  4. # 最开始假设它是有序的
  5. is_sorted = True
  6. # 一次比较两个,跳过头部
  7. node = numbers.begin.next
  8. while node:
  9. # 遍历并将当前节点与上一个比较
  10. if node.prev.value > node.value:
  11. # 如果上一个更大,我们需要交换
  12. node.prev.value, node.value = node.value, node.prev.value
  13. # 这表示我们需要再次扫描
  14. is_sorted = False
  15. node = node.next
  16. # 它在顶部重置过,但是如果我们没有交换,那么它是有序的
  17. if is_sorted: break

我在这里添加了其他注释,以便你可以学习并跟踪它,将我在此处完成的内容与伪代码进行比较。你还应该看到,维基百科页面正在使用的数据结构,与DoubleLinkedList完全不同。维基百科的代码假设在数组或列表结构上实现函数。你必须将下面这行:

  1. if A[i-1] > A[i] then

使用DoubleLinkedList翻译为 Python:

  1. if node.prev.value > node.value:

我们不能轻易地随机访问DoubleLinkedList,所以我们必须将这些数组索引操作转换为.next.prev。在循环中,我们还必须注意nextprev属性是否是None。这种转换需要大量的翻译,学习和猜测你正在阅读的伪代码的语义。

学习冒泡排序

你现在应该花时间研究这个bubble_sortPython 代码,看看我如何翻译它。确保观看我实时的视频,并获得更多的透视。你还应该绘制在不同类型的列表(已排序,随机,重复等)上运行的图表。一旦你了解我是如何做到的,为此研究pytestmerge_sort算法:

  1. import sorting
  2. from dllist import DoubleLinkedList
  3. from random import randint
  4. max_numbers = 30
  5. def random_list(count):
  6. numbers = DoubleLinkedList()
  7. for i in range(count, 0, -1):
  8. numbers.shift(randint(0, 10000))
  9. return numbers
  10. def is_sorted(numbers):
  11. node = numbers.begin
  12. while node and node.next:
  13. if node.value > node.next.value:
  14. return False
  15. else:
  16. node = node.next
  17. return True
  18. def test_bubble_sort():
  19. numbers = random_list(max_numbers)
  20. sorting.bubble_sort(numbers)
  21. assert is_sorted(numbers)
  22. def test_merge_sort():
  23. numbers = random_list(max_numbers)
  24. sorting.merge_sort(numbers)
  25. assert is_sorted(numbers)

这个测试代码的一个重要部分是,我正在使用random.randint函数生成随机数据进行测试。这个测试不会测试许多边界情况,但这是一个开始,我们将在以后进行改进。记住,你没有实现sort.merge_sort,所以你可以不写这个测试函数,或者现在注释它。

一旦你进行了测试,并且写完了这个代码,再次研究维基百科页面,然后在尝试merge_sort之前,尝试一些其他的bubble_sort版本。

归并排序

我还没准备好让你自己实现它。我将再次对merge_sort函数重复此过程,但是这次我想让你尝试,从归并排序的维基百科页面 上的伪代码中实现该算法,然后再查看我怎么做。有几个建议的实现,但我使用“自顶向下”的版本:

  1. function merge_sort(list m)
  2. if length of m 1 then
  3. return m
  4. var left := empty list
  5. var right := empty list
  6. for each x with index i in m do
  7. if i < (length of m)/2 then
  8. add x to left
  9. else
  10. add x to right
  11. left := merge_sort(left)
  12. right := merge_sort(right)
  13. return merge(left, right)
  14. function merge(left, right)
  15. var result := empty list
  16. while left is not empty and right is not empty do
  17. if first(left) first(right) then
  18. append first(left) to result
  19. left := rest(left)
  20. else
  21. append first(right) to result
  22. right := rest(right)
  23. while left is not empty do
  24. append first(left) to result
  25. left := rest(left)
  26. while right is not empty do
  27. append first(right) to result
  28. right := rest(right)
  29. return result

test_merge_sort编写剩余测试用例函数,然后在这个实现上进行尝试。我会给你一个线索,当仅仅使用第一个DoubleLinkedListNode时,该算法效果最好。你也可能需要一种方法,从给定的节点计算节点数。这是DoubleLinkedList不能做的事情。

归并排序作弊模式

如果你尝试了一段时间并且需要作弊,这是我所做的:

  1. def count(node):
  2. count = 0
  3. while node:
  4. node = node.next
  5. count += 1
  6. return count
  7. def merge_sort(numbers):
  8. numbers.begin = merge_node(numbers.begin)
  9. # horrible way to get the end
  10. node = numbers.begin
  11. while node.next:
  12. node = node.next
  13. numbers.end = node
  14. def merge_node(start):
  15. """Sorts a list of numbers using merge sort."""
  16. if start.next == None:
  17. return start
  18. mid = count(start) // 2
  19. # scan to the middle
  20. scanner = start
  21. for i in range(0, mid-1):
  22. scanner = scanner.next
  23. # set mid node right after the scan point
  24. mid_node = scanner.next
  25. # break at the mid point
  26. scanner.next = None
  27. mid_node.prev = None
  28. merged_left = merge_node(start)
  29. merged_right = merge_node(mid_node)
  30. return merge(merged_left, merged_right)
  31. def merge(left, right):
  32. """Performs the merge of two lists."""
  33. result = None
  34. if left == None: return right
  35. if right == None: return left
  36. if left.value > right.value:
  37. result = right
  38. result.next = merge(left, right.next)
  39. else:
  40. result = left
  41. result.next = merge(left.next, right)
  42. result.next.prev = result
  43. return result

在尝试实现它时,我将使用此代码作为“备忘单”来快速获取线索。你还会看到,我在视频中尝试从头开始重新实现此代码,因此你可以看到我努力解决你可能遇到过的相同问题。

快速排序

最后,轮到你尝试实现quick_sort并创建test_quicksort测试用例。我建议你首先使用 Python 的普通列表类型实现简单的快速排序。这将有助于你更好地理解它。然后,使用简单的 Python 代码,并使其处理DoubleLinkedList(的头节点)。记住要把你的时间花费在这里,显然还要在你的test_quicksort里进行大量的调试和测试。

深入学习

  • 这些实现在性能上绝对不是最好的。尝试写一些丧心病狂的测试来证明这一点。你可能需要将一个很大的列表传给算法。使用你的研究来找出病态(绝对最差)的情况。例如,当你把一个有序的列表给quick_sort时会发生什么?
  • 不要实现任何改进,但研究你可以对这些算法执行的,各种改进方法。
  • 查找其他排序算法并尝试实现它们。
  • 它们还可以在SingleLinkedList上工作吗?QueueStack呢?它们很实用吗?
  • 了解这些算法的理论速度。你会看到O(n^2)O(nlogn)的引用,这是一种说法,在最坏的情况下,这些算法的性能很差。为算法确定“大O”超出了本书的范围,但我们将在练习 18 中简要讨论这些度量。
  • 我将这些实现为一个单独的模块,但是将它们作为函数,添加到DoubleLinkedList更简单吗?如果你这样做,那么你需要将该代码复制到可以处理的其他数据结构上吗?我们没有这样的设计方案,如何使这些排序算法处理任何“类似链表的数据结构”。
  • 再也不要使用气泡排序。我把它包含在这里,因为你经常遇到坏的代码,并且我们会在练习 19 中提高其性能。