787. 归并排序

发表于2022-02-18更新于2024-09-15字数统计611阅读时长6分阅读次数

摘要
Title: 787. 归并排序
Tag: 归并排序
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

787. 归并排序

题意

给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

思路

  • 三个步骤

    • 确定分界点
    • 递归
    • 归并

  • 核心思想

    • 分治

    img

代码

更新写法（不用进行扫尾工作）

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
'''
Author: NEFU AB-IN
Date: 2022-02-18 11:33:11
FilePath: \ACM\Acwing\787.py
LastEditTime: 2022-02-18 19:20:56
'''
a = []


def mergesort(l, r):
    if l >= r:
        return
    mid = l + r >> 1
    mergesort(l, mid)
    mergesort(mid + 1, r)
    tmp = []
    i, j = l, mid + 1

    while i <= mid or j <= r:
        if j == r + 1 or i <= mid and a[i] <= a[j]:
            tmp.append(a[i])
            i += 1
        else:
            tmp.append(a[j])
            j += 1
    a[l:r + 1] = tmp

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    mergesort(0, n - 1)
    for i in a:
        print(i, end=" ")

带注释版

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
36
37
'''
Author: NEFU AB-IN
Date: 2022-02-18 11:33:11
FilePath: \ACM\Acwing\787.py
LastEditTime: 2022-02-18 11:36:48
'''
a = []


def mergesort(l, r):
    if l >= r: #当区间只剩0或1个数是return
        return
    mid = l + r >> 1 #确定中间下标为分界点，快排是确定一个数
    mergesort(l, mid) #先递归
    mergesort(mid + 1, r)
    tmp = [] #归并数组
    i, j, = l, mid + 1 #i，j分别为左右两个区间的起始点

    while i <= mid and j <= r:
        if a[i] <= a[j]: #当a[i]小的时候，a[i]加入归并数组
            tmp.append(a[i])
            i += 1
        else:
            tmp.append(a[j])
            j += 1
    tmp += a[i:mid + 1] #当其中一个区间遍历完了，另一个区间可能为遍历完，归并数组需要加上剩余的
    tmp += a[j:r + 1]
    a[l:r + 1] = tmp #将归并数组赋给原数组


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    mergesort(0, n - 1)
    for i in a:
        print(i, end=" ")

无注释版

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
36
37
38
'''
Author: NEFU AB-IN
Date: 2022-02-18 11:33:11
FilePath: \ACM\Acwing\787.py
LastEditTime: 2022-02-18 11:36:48
'''
a = []


def mergesort(l, r):
    if l >= r:
        return
    mid = l + r >> 1
    mergesort(l, mid)
    mergesort(mid + 1, r)
    tmp = []
    i, j, = l, mid + 1

    while i <= mid and j <= r:
        if a[i] <= a[j]:
            tmp.append(a[i])
            i += 1
        else:
            tmp.append(a[j])
            j += 1
    tmp += a[i:mid + 1]
    tmp += a[j:r + 1]
    a[l:r + 1] = tmp


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    mergesort(0, n - 1)
    for i in a:
        print(i, end=" ")

使用搜索：谷歌必应百度