Py008-01-11归并排序之归并

归并排序——归并

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

1
如[2,5,7,8,9|华丽的分割线|1,3,4,6]
  • 这种操作称为一次归并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
res = []
两个列表分别取第一个
[2,5,7,8,9] 
[1,3,4,6]
2>1 1出来 res = [1]
[2,5,7,8,9] 
[3,4,6]
2<3 2出来 res = [1,2]
[5,7,8,9] 
[3,4,6]
5>3 3出来 res = [1,2,3]
[5,7,8,9] 
[4,6]
5>4 4出来 res = [1,2,3,4]
[5,7,8,9] 
[6]
5<6 5出来 res = [1,2,3,4,5]
[7,8,9] 
[6]
7>6 6出来 res = [1,2,3,4,5,6]
[7,8,9] 
[]
[7,8,9] 都出来 res = [1,2,3,4,5,6,7,8,9]

代码实现

  • 大前提：两段有序的归并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def merge(li,low,mid,high):
    i = low # 第一个列表起点
    j = mid+1 # 第二个列表起点
    ltmp = [] # 没法用到原地排序了
    while i<=mid and j<=high:# 只要左右两边都有数
        if li[i] < li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1

    # while执行完了，肯定有一头 没数了
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high+1] = ltmp

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

归并排序——使用归并

  • 分解：将列表越分越小，直至分成一个元素
  • 终止条件：一个元素是有序的
  • 合并：将两个有序列表归并，列表越来越大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def merge(li,low,mid,high):
    i = low # 第一个列表起点
    j = mid+1 # 第二个列表起点
    ltmp = [] # 没法用到原地排序了
    while i<=mid and j<=high:# 只要左右两边都有数
        if li[i] < li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1

    # while执行完了，肯定有一头 没数了
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high+1] = ltmp


def merge_sort(li,low,high):
    if low < high:#至少有两个元素，递归
        mid = (low + high)//2
        merge_sort(li,low,mid)
        merge_sort(li,mid+1,high)
        merge(li,low,mid,high)

li = list(range(16))
import random
random.shuffle(li)
print(li)
merge_sort(li,0,len(li)-1)
print(li)

归并排序复杂度

时间复杂度

  • O(nlogn)

空间复杂度

  • O(n) 因为不是原地排序需要单独开辟空间