本文共 1536 字，大约阅读时间需要 5 分钟。

1.问题分析

合并排序问题给定的是一个无序的序列，可以把待排序的元素分解为两个规模大致相等的子序列。如果还是不容易解决就继续将子序列分解，直到子序列中的元素个数为1，因为单个元素的序列本身是有序的，此时便可以进行合并，从而得到一个完整的有序序列。 2.算法设计 （1）分解：将待排序元素分成大小大致相同的两个子序列。 （2）治理：对两个子序列进行合并。 （3）合并：将排好序的有序子序列进行合并，得到最终的有序序列。 3.过程描述 4.程序代码

def Merge(A,low,mid,high):    B = [None for i in range(0,high-low+1)]  #定义一个列表    i = low    j = mid + 1    k = 0    while(i <= mid and j <= high):        #按照从小到大的顺序存放到列表B中        if(A[i] <= A[j]):            B[k] = A[i]            i += 1            k += 1        else:            B[k] = A[j]            j += 1            k += 1    while(i <= mid):        #将子序列A[low:middle]剩余元素的依次复制到B中        B[k] = A[i]        i += 1        k += 1    while(j <= high):        # 将子序列A[middle+1:high]剩余的元素依次复制到B中        B[k] = A[j]        j += 1        k += 1    temp = 0    for i in range(low,high+1):        #将合并后的序列复制到原来的A[]序列        A[i] = B[temp]        temp += 1    del Bdef MergeSort(A,low,high):    if low < high:        mid = (low + high) // 2        MergeSort(A,low,mid)       #对A[low:mid]中的元素合并排序        MergeSort(A,mid + 1,high)  #对A[mid+1:high]中的元素合并排序        Merge(A,low,mid,high)      #合并操作if __name__ == '__main__':    A = []    n = int(input('请输入数列中的元素个数n为：'))    for i in range(n):        A.append(int(input('请依次输入数列中的元素：')))    MergeSort(A,0,n-1)    print('合并排序结果为：')    for i in range(n):        print(A[i],'\t',end='')

5.运行结果

请输入数列中的元素个数n为：8请依次输入数列中的元素：3请依次输入数列中的元素：1请依次输入数列中的元素：5请依次输入数列中的元素：2请依次输入数列中的元素：6请依次输入数列中的元素：4请依次输入数列中的元素：8请依次输入数列中的元素：7合并排序结果为：1 	2 	3 	4 	5 	6 	7 	8

6.复杂度分析

时间复杂度O(n logn) 空间复杂度O(n)

转载地址：http://hncii.baihongyu.com/