分治法
很多有用的算法结构上是递归的，为了解决一个特定的问题，算法一次或者多次递归调用其自身以解决若干子问题。这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但是类似于原问题的子问题，递归求解这些子问题，然后再合并这些问题的解来建立原问题的解。
分治法在每层递归时有三个步骤:
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)
