每天学一个算法之归并排序

归并算法（MERGE-SORT）（设按升序排列）1、分冶法—分冶思想的介绍将原始问题分解为几个规模较小但类似于原问题容易解决的子问题，递归地求解这些子问题，然后再合并子问题的解来建立原始问题的解。分冶法在递归时的步骤分解： 原问题分解为子问题，子问题是原问题规模较小的实例。解决： 递归地解决子问题，若子问题足够小，则直接求解。合并： 合并子问题的解。得到原问题解。在归并排序中的体现分解： 分解待排序的n个元素的序列成各自具有n/2个元素的两个子序列。解决： 使用归并排序递归地排序两个子序列。合并： 合并两个已排序的子序列一产生最终已排序的序列。2、 归并排序伪代码描述主过程： MERGE-SORT(A, startIndex, endIndex), A: 待排数组 startIndex： 起始数组下标 endIndex： 截止数组下标MERGE-SORT(A, startIndex, endIndex) if startIndex < endIndex midIndex = (startIndex + endIndex)/2 // midIndex取(startIndex + endIndex)/2值的底; MERGE-SORT(A, startIndex ,midIndex) MERGE-SORT(A, midIndex + 1,endIndex) MERGE(A, startIndex, midIndex, endIndex)子过程： MERGE(A, startIndex, midIndex, endIndex)MERGE(A, startIndex, midIndex, endIndex) n1 = midindex - startIndex + 1 n2 = endIndex - midIndex let L[1..n1+1] and R[1..n2+1] be new arrays for i = 1 to n1 L[i] = A[startIndex + i -1] for j = 1 to n2 R[j] = A[midIndex + j] L[n1+1] = Infinity R[n2+1] = Infinity i = 1 j = 1 for k = startIndex to endIndex if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1