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

## 挑战练习

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


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


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


if node.prev.value > node.value:


### 学习冒泡排序

import sorting
from dllist import DoubleLinkedList
from random import randint

max_numbers = 30

def random_list(count):
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)


### 归并排序

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不能做的事情。

### 归并排序作弊模式

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

• #### Python进阶

东滨社 python 73页 2018年6月8日
2664

• #### Seaborn 0.9 中文文档

ApacheCN python 76页 2019年5月26日
32

• #### pyspider中文文档

aaronhua123 python 18页 2019年5月12日
1

• #### Influxdb 简明手册 教程 入门 文档

tzivanmoe influxdb 18页 2018年7月1日
0

• #### C 语言编程透视

泰晓科技 c 13页 2018年5月30日
369

• #### C++ 资源大全中文版

伯乐在线 cplusplus 1页 2018年6月6日
1422