Python3 归并排序

我就是我 2023-05-29 03:08 1阅读 0赞

参考：菜鸟教程  [https://www.runoob.com/python3/python-merge-sort.html][https_www.runoob.com_python3_python-merge-sort.html]

$ 归并排序(Merge sort)  
采用分治法(Divide and Conquer)，  
(1)分割：递归地把当前序列平均分割成两半  
(2)集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）

\[分割\] 初始列表分成列表A和列表B,如果分别已排好序，事情就好办了  
<- 解决A和B排序的问题，即分别把A和B各自再分成两个子列表,以此类推  
<- 满足基线条件，子列表一个只有一个元素，另一个只有1个元素或为空  
\[集成\] 创建临时列表C,将A和B中的元素比较，从大到小append进列表C,完成！

$ 归并排序代码实现

def merge(arr, l, m, r):    #在arr中选取一段，l为起始元素索引，r为结束元素索引。如果给arr整个排序，l=0，r=len(arr)-1
        n1 = m - l + 1          #m为arr[l]和arr[r]之间的一个元素的索引，此处分段的时候放在前面那个列表
        n2 = r- m               #前面的子列表n1个元素，后面的子列表n2个元素
      
        # 创建临时数组
        L = [0] * (n1)
        R = [0] * (n2)
      
        # 拷贝数据到临时数组 arrays L[] 和 R[] 
        for i in range(0 , n1): 
            L[i] = arr[l + i] 
      
        for j in range(0 , n2): 
            R[j] = arr[m + 1 + j] 
      
        # 归并临时数组到 arr[l..r] 
        i = 0     # 初始化第一个子数组的索引
        j = 0     # 初始化第二个子数组的索引
        k = l     # 初始归并子数组的索引，是小写的L
      
        while i < n1 and j < n2 : 
            if L[i] <= R[j]: 
                arr[k] = L[i] 
                i += 1
            else: 
                arr[k] = R[j] 
                j += 1
            k += 1
      
        # 拷贝 L[] 的保留元素
        while i < n1: 
            arr[k] = L[i] 
            i += 1
            k += 1
      
        # 拷贝 R[] 的保留元素
        while j < n2: 
            arr[k] = R[j] 
            j += 1
            k += 1
      
    def mergeSort(arr,l,r): 
        if l < r: 
            m = int((l+(r-1))/2)  
            mergeSort(arr, l, m) 
            mergeSort(arr, m+1, r) 
            merge(arr, l, m, r) 
    
    arr = [12, 11, 13, 5, 6, 7] 
    n = len(arr) 
    print ("给定的数组") 
    for i in range(n): 
        print ("%d" %arr[i]), 
      
    mergeSort(arr,0,n-1) 
    print ("\n\n排序后的数组") 
    for i in range(n): 
        print ("%d" %arr[i])

[https_www.runoob.com_python3_python-merge-sort.html]: https://www.runoob.com/python3/python-merge-sort.html