Python数据结构与算法9——归并排序

归并排序

算法思想

归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。
https://www.cnblogs.com/onepixel/articles/7674659.html

栗子

image.png

时间复杂度

时间复杂度是

代码实现

# coding: utf-8

def merge_sort(alist):
    # 归并排序
    n = len(alist)
    # 当长度小于1，直接返回
    if n <= 1:
        return alist
    
    # 取整函数，将原数据分成两个部分
    mid = n // 2
    # 采用归并排序后形成的左边有序新序列
    left_li = merge_sort(alist[:mid])
    
    # 采用归并排序后形成的右边有序新序列
    right_li = merge_sort(alist[mid:])
    
    # 将两个有序的子序列进行合并
    # merge(left, right)
    left_pointer, right_pointer = 0, 0
    result = []
    
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] < right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1
    
    # 若某边已合并完毕，某边还有剩下，直接将该边中的元素追加到列表         
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result

li = [2, 9, 7 ,4, 8, 5, 10, 3, 1, 6]
print("排序前li:", li)
sort_li = merge_sort(li)
print("排序后li:", li)
print("返回值:", sort_li)

image.png

# baidubaike

def MergeSort(lists):
    if len(lists) <= 1:
        return lists
    
    # 分成两半数据
    num = int( len(lists) / 2 )
    left = MergeSort(lists[:num])
    right = MergeSort(lists[num:])
    return Merge(left, right)

# 合并函数
def Merge(left,right):
    r, l=0, 0
    result=[]
    while l<len(left) and r<len(right):
        # 若左边小于右边，追加到左边列表，指针右移
        if left[l] <= right[r]:
            result.append(left[l])
            l += 1
        else:
            # 反之追加到右边，同时指针右移
            result.append(right[r])
            r += 1
            
    # 如果某边的元素还有剩余直接全部追击到列表中
    result += list(left[l:])
    result += list(right[r:])
    return result
print (MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45]))