Python 算法 | 归并排序

将原数组不断分解为前后两部分, 直到每个数组内只有一个元素, 然后不断进行排序合并, 最后合并为一个有序数组

分析

假设现在的列表分两段有序，如何将其合成为一个有序列表。

思路：
　　比较2个列表第一个元素，谁小，谁出来。继续比剩下2个列表的首元素，直到2边只剩下一边是有元素的，另外一边是没有元素的。然后把有元素的一边依次取出来，最后就是一个有序列表了。这种操作称为一次归并。

image image image

完整代码

def merge(li, low, mid, high):
    # 列表两段有序: [low, mid] [mid+1, high]
    i = low
    j = mid + 1
    li_tmp = []
    while i <= mid and j <= high:
        if li[i] <= li[j]:
            li_tmp.append(li[i])
            i += 1
        else:
            li_tmp.append(li[j])
            j += 1
    while i <= mid:
        li_tmp.append(li[i])
        i += 1
    while j <= high:
        li_tmp.append(li[j])
        j += 1

    li[low:high+1] = li_tmp

li = [2,5,7,9,1,3,4,6,8]
merge(li,0,3,8)
print(li)
'''
[1, 2, 3, 4, 5, 6, 7, 8, 9]
'''

时间复杂度O(n)

扩展

两个有序列表，合并成一个有序列表（注意是2个，而不是上面的一个两段有序的列表）。整体思路和上面差不多。

def merge2list(li1, li2):
    li = []
    i = 0                                 # i表示li1列表的索引
    j = 0                                 # j表示li2列表的索引
    while i < len(li1) and j < len(li2):  # li1和li2列表里面有值
        if li1[i] <= li2[j]:
            li.append(li1[i])
            i += 1
        else:
            li.append(li2[j])
            j += 1
    while i < len(li1):                  #li1列表里面有剩余值
        li.append(li1[i])
        i += 1
    while j < len(li2):                  # li2列表里面有剩余值     
        li.append(li2[j])
        j += 1
    return li

li1 = [2,5,7,9]
li2 = [1,3,4,6,8]
li = merge2list(li1,li2)
print(li)                               # [1, 2, 3, 4, 5, 6, 7, 8, 9]

有了归并怎么用？
分解：将列表越分越小，直至分成一个元素。
终止条件：一个元素是有序的。
合并：将两个有序列表归并，列表越来越大。

image

归并排序
　　在low和high之间一半处递归继续往下分，然后使用上面的一次归并。先递归后执行比先执行后递归慢。

def merge(li, low, mid, high):
    # 列表两段有序: [low, mid] [mid+1, high]
    i = low
    j = mid + 1
    li_tmp = []                                 # x
    while i <= mid and j <= high:               #
        if li[i] <= li[j]:
            li_tmp.append(li[i])
            i += 1
        else:
            li_tmp.append(li[j])
            j += 1
    while i <= mid:
        li_tmp.append(li[i])
        i += 1
    while j <= high:
        li_tmp.append(li[j])
        j += 1
    # li_tmp[0:high-low+1] li[low:high+1]
    # for i in range(low, high+1):
    #     li[i] = li_tmp[i-low]
    li[low:high+1] = li_tmp




def _merge_sort(li, low, high):         # 排序li的low到high的范围
    if low < high:
        mid = (low + high) // 2
        _merge_sort(li, low, mid)
        _merge_sort(li, mid+1, high)
        # print(li[low:mid + 1], li[mid + 1:high + 1])
        merge(li, low, mid, high)
        # print(li[low: high + 1])

@cal_time
def merge_sort(li):
    _merge_sort(li, 0, len(li)-1)

li = list(range(100000))
li.sort()
random.shuffle(li)
merge_sort(li)
#print(li)

• 时间复杂度:
  可以理解为不断的从中间分解需要O(logn)次, 每次都需要对n个元素排序, 所以需要O(nlogn)空间复杂度: O(n)
  • 最好: O(nlogn)
  • 最坏: O(nlogn)
  • 平均: O(nlogn)
• 空间复杂度
  虽然每次排序都需要申请内存, 但是使用完毕后都释放了, 最多的一次使用内存是O(n)