算法导论-归并排序算法导论-归并排序

1.伪代码

'''MERGE(A,p,q,r)''' n1 = q - p + 1//L.length n2 = r - q//R.length let L[1..n1+1] and R[1..n2+1] be new arrays for i = 1 to n1 L[i] = A[p + i - 1] for j = 1 to n2 R[j] = A[q + j] L[n1 + 1] = ∞ R[n2 + 1] = ∞ i = 1 j = 1 for k = p to r if L[i] <= R[j] A[k] = L[I] i = i + 1 else A[k] = R[j] j = j + 1

'''MERGE-SORT(A, p, r)''' if p < r q = [(p+r)/2] MERGE-SORT(A, p, q) MERGE-SORT(A, q+1, r) MERGE(A,p,q,r)

MERGE算法图示

文章图片
2.Python代码

def merge(A, p, q, r): #A[p:q+1],A[q+1:r+1] L = A[p:q+1] R = A[q+1:r+1] i = 0 j = 0 for k in range (p, r+1): if i < len(L) and j < len(R): if L[i] <= R[j]: A[k] = L[I] i = i + 1 else: A[k] = R[j] j = j + 1 elif i < len(L): A[k] = L[I] i = i + 1 else: A[k] = R[j] j = j + 1 return A

def merge_sort(A, p ,r): if p < r: q = (p+r)/2 merge_sort(A, p, q) merge_sort(A, q+1, r) merge(A,p,q,r)

result:

Before: [34, 45, 12, 32, 100, 46, 82, 11] After: [11, 12, 32, 34, 45, 46, 82, 100]

循环不变性对于归并算法

初始化: 在循环之前,子数组为空,L和R数组升序排列, i=j=1, 分别指向数组最小值
保持: 每次循环从L和R中取出当前指向两者中小的值,此值为L和R所有值中的最小值,被取用值的数组的指针向后指,保证L和R是为归并的值,此时子数组升序排列且最大值 <= L和R的最小值
终止: 结束时子数组,L和R数组均指向数组最大值,此时子数组为L和R中的数值升序排列

归并算法递归部分:MERGE_SORT(A,p,r) 递归二分数组,直到p<=r, 即细分到单元素数组,所以已经排好序.
递归归并子数组,直到将所有数据合并完.
MERGE_SORT算法图示