程序员的数学之递归归并排序

发表于 | 分类于 | 阅读次数:
字数统计: 407 | 阅读时长 ≈ 1

分治问题 适合于使用递归实现

帮助设计分布式系统和并行计算，细分后的问题交给不同的机器来处理

某些机器专门负责收集来自不同机器的处理结果 完成结果的合并

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


# coding=utf-8
import copy


def merge_sort(to_sort=None):
    """
    使用函数的递归（嵌套）调用，实现归并排序（从小到大）
    :param to_sort: 等待排序的数组
    :return: 排序后的数组
    """
    if to_sort is None:
        return []
    # 如果分解到只剩一个数，返回该数
    if len(to_sort) == 1:
        return to_sort
    # 将数组分解成左右两半
    mid = len(to_sort) // 2  # python3 // 表示整除，不带小数
    left = copy.copy(to_sort[0:mid])
    right = copy.copy(to_sort[mid:len(to_sort)])
    # 嵌套调用 对两半数组分别进行排序
    left = merge_sort(left)
    right = merge_sort(right)
    # 合并排序后的两半
    merged = merge(left, right)

    return merged


def merge(left=None, right=None):
    """
    合并两个已经排序完毕的数组（从小到大）
    :param left: 左半边数组
    :param right: 右半边数组
    :return: 合并后的数组
    """
    if left is None:
        left = []
    if right is None:
        right = []
    merged_one = list()
    ai = 0
    bi = 0
    # 轮流从两个数组中取出较小的值 放入合并后的数组中
    while ai < len(left) and bi < len(right):
        if left[ai] <= right[bi]:
            merged_one.append(left[ai])
            ai = ai + 1
        else:
            merged_one.append(right[bi])
            bi = bi + 1
    # 将某个数组内剩余的数字放入合并后的数组中
    if ai < len(left):
        for i in range(ai, len(left)):
            merged_one.append(left[i])
    else:
        for i in range(bi, len(right)):
            merged_one.append(right[i])
    return merged_one


if __name__ == '__main__':
    to_sort_ = [7,6,2,4,1,9,3,8,0,5]
    sorted_ = merge_sort(to_sort_)
    print(sorted_)