分治法
很多有用的算法結構上是遞歸的，為了解決一個特定的問題，算法一次或者多次遞歸調用其自身以解決若幹子問題。這些算法典型地遵循分治法的思想:将原問題分解為幾個規模較小但是類似于原問題的子問題，遞歸求解這些子問題，然後再合并這些問題的解來建立原問題的解。
分治法在每層遞歸時有三個步驟:
1.分解原問題為若幹子問題，這些子問題是原問題的規模最小的執行個體
2.解決這些子問題，遞歸地求解這些子問題。當子問題的規模足夠小，就可以直接求解
3.合并這些子問題的解成原問題的解
歸并排序
現在我們就來看下歸并排序是如何利用分治法解決問題的。 1.分解:将待排序的n個元素分成各包含n/2個元素的子序列 2.解決:使用歸并排序遞歸排序兩個子序列 3.合并:合并兩個已經排序的子序列以産生已排序的答案 考慮到我們排序這個數組:[10,23,51,18,4,31,13,5],我們遞歸地将數組進行分解
當數組被完全分隔成隻有單個元素的數組時，我們需要把它們合并回去，每次兩兩合并成一個有序的序列.
上圖關于下标指針歸并兩個數組的具體實作原理:
def merge_sort(seq):
if len(seq) <= :
return seq
else:
mid = int(len(seq)/)
left_half = merge_sort(seq[:mid])
right_half = merge_sort(seq[mid:])
#合并兩個有序數組
new_seq = merge_sorted_list(left_half,right_half)
return new_seq
def merge_sorted_list(sorted_a,sorted_b):
length_a,length_b = len(sorted_a),len(sorted_b)
#定義兩個有序數組的指針即下标
a = b =
new_sorted_seq = list()
while a < length_a and b < length_b:
if sorted_a[a] < sorted_b[b]:
new_sorted_seq.append(sorted_a[a])
a +=
else:
new_sorted_seq.append(sorted_b[b])
b +=
while a < length_a:
new_sorted_seq.append(sorted_a[a])
a +=
while b < length_b:
new_sorted_seq.append(sorted_b[b])
b +=
return new_sorted_seq
def test_merge_sort():
import random
seq = list(range())
#shuffle()函數打亂數組序列
random.shuffle(seq)
assert merge_sort(seq) = sorted(seq)
