Python3排序算法05 - 归并排序

  • 原创
  • Madman
  • /
  • 2018-09-15 17:35
  • /
  • 0
  • 87 次阅读

Synopsis: 归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法,它将已经有序的子序列合并,得到完全有序的序列。也就是说,先使每个子序列有序(单个元素组成的序列肯定是有序的),再将两个有序序列合并成一个更大的有序序列。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,将复杂的问题分解成容易解决的小问题,比如将两个只有一个元素的左右子序列排序合并很简单,再一层层合并成更大的有序序列

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 算法介绍

归并排序(Merge Sort)算法于1945年由约翰·冯·诺伊曼首次提出,它是采用分治法(Divide and Conquer)的一个典型的应用,是创建在归并操作(Merge)上的一种有效的排序算法,时间复杂度为O(n log n)

2. Python实现

归并排序算法依赖归并操作。归并操作是将 两个已经排序的序列 合并成一个序列的操作:

def merge(left, right):
    '''归并操作,使用可移动游标'''
    left_index = 0  # left序列的可移动的下标
    right_index = 0  # right序列的可移动的下标
    merged = []  # 用来存放最终排好序的元素

    while left_index < len(left) and right_index < len(right):  # 一旦 left序列 或 right序列 中的元素比较完成,就退出循环
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1  # left序列的下标向右移动一位
        else:
            merged.append(right[right_index])
            right_index += 1  # right序列的下标向右移动一位

    merged = merged + left[left_index:]  # 如果 left序列 还有没比较的元素
    merged = merged + right[right_index:]  # 如果 right序列 还有没比较的元素
    return merged

或者:

from collections import deque

def merge(left, right):
    '''归并操作,使用deque'''
    merged, left, right = [], deque(left), deque(right)

    while left and right:
        merged.append(left.popleft() if left[0] <= right[0] else right.popleft())  # deque popleft is also O(1)
    merged.extend(right if right else left)  # 如果 left序列 还有没比较的元素

    return merged

2.1 递归法 - 自顶向下(Top Down)

def merge_sort(L):
    n = len(L)
    # 两个作用:
    # 1. 客户端传入原始序列只有一个元素或为空时,不用排序,直接返回
    # 2. 递归的退出条件。如果传入的序列元素个数为1时,不再拆分,返回
    if n <= 1:
        return L

    # 将传入的序列拆分成左右两个子序列,再分别递归
    mid = n // 2
    left = merge_sort(L[:mid])  # 特别注意:先递归左边的,直到子序列元素为1个,才依次向上返回。比如L = [54, 26, 93, 17, 77, 31, 44, 55, 20],则会先将 [54, 26, 93, 17] 归并排序好之后才会排右边的
    right = merge_sort(L[mid:])

    # 开始执行归并操作,将结果返回给上一层的 merge_sort() 调用栈
    return merge(left, right)


def merge(left, right):
    '''归并操作,使用可移动游标'''
    left_index = 0  # left序列的可移动的下标
    right_index = 0  # right序列的可移动的下标
    merged = []  # 用来存放最终排好序的元素

    while left_index < len(left) and right_index < len(right):  # 一旦 left序列 或 right序列 中的元素比较完成,就退出循环
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1  # left序列的下标向右移动一位
        else:
            merged.append(right[right_index])
            right_index += 1  # right序列的下标向右移动一位

    merged = merged + left[left_index:]  # 如果 left序列 还有没比较的元素
    merged = merged + right[right_index:]  # 如果 right序列 还有没比较的元素
    return merged


def is_sorted(L):
    '''辅助函数: 用来判断 '归并排序函数(merge_sort)' 的输出结果是否是正确的升序序列'''
    prev = L[0]
    for i in range(1, len(L)):
        if prev > L[i]:
            print('Sort ascending failed.')
            return False
        prev = L[i]
    print('Sort ascending succeed.')
    return True


if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    merged = merge_sort(L1)
    if is_sorted(merged):
        print('After: ', merged)

# Output:
Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
Sort ascending succeed.
After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

Merge Sort 01

过程分析:

Step 1: 对应上图中标号1,执行 merged = merge_sort([54, 26, 93, 17, 77, 31, 44, 55, 20]) 时,n = 9mid = 4

执行到 left = merge_sort([54, 26, 93, 17]) 后,将会第1次递归执行merge_sort函数,所以后续的 right = merge_sort([77, 31, 44, 55, 20]) 暂时不会执行

Step 2: 对应上图中标号2,(第1次递归)执行 left = merge_sort([54, 26, 93, 17]) 时,n = 4mid = 2

执行到 left = merge_sort([54, 26]) 后,将会第2次递归执行 merge_sort 函数

Step 3: 对应上图中标号3,(第2次递归)执行 left = merge_sort([54, 26]) 时,n = 2mid = 1

执行到 left = merge_sort([54])时,将会第3次递归执行 merge_sort 函数

Step 4: 对应上图中标号4,(第3次递归)执行 left = merge_sort([54]) 时,n = 1,返回 [54],第3次递归结束! 所以 left = [54]

Step 5: 对应上图中标号5,返回到第2次递归中,执行 right = merge_sort([26])时,将会第4次递归执行 merge_sort 函数

Step 6: 对应上图中标号6,(第4次递归)执行 right = merge_sort([26]) 时,n = 1,返回 [26],第4次递归结束! 所以 right = [54]

此时,会返回到第1次递归中,执行 return merge(left, right),将会执行第1次归并操作

Step 7: 对应上图中标号7,(第1次归并)开始归并操作,结果为 [26, 54],所以 left = merge_sort([54, 26]) 的结果为 left = [26, 54]

Step 8: 对应上图中标号8,继续在第1次递归中往下执行,执行 right = merge_sort([93, 17])时,将会第5次递归执行 merge_sort 函数

Step 9: 对应上图中标号9,(第5次递归)执行 right = merge_sort([93, 17]) 时,n = 2mid = 1

执行到 left = merge_sort([93])后,将会第6次递归执行 merge_sort 函数

Step 10: 对应上图中标号10,(第6次递归)执行 left = merge_sort([93]) 时,n = 1,返回 [93],第6次递归结束! 所以 left = [93]

Step 11: 对应上图中标号11,此时,会返回到第5次递归中,执行 right = merge_sort([17])时,将会第7次递归执行 merge_sort 函数

Step 12: 对应上图中标号12,(第7次递归)执行 right = merge_sort([17]) 时,n = 1,返回 [17],第7次递归结束! 所以 right = [17]

此时,会返回到第5次递归中,执行 return merge(left, right),将会执行第2次归并操作

Step 13: 对应上图中标号13,(第2次归并)开始归并操作,结果为 [17, 93],所以 right = merge_sort([93, 17]) 的结果为 right = [17, 93]

继续在第1次递归中往下执行,执行 return merge(left, right),将会执行第3次归并操作

Step 14: 对应上图中标号14,(第3次归并)开始归并操作,结果为 [17, 26, 54, 93], 所以 left = merge_sort([54, 26, 93, 17]) 的结果为 right = [17, 26, 54, 93]

继续返回到 Step 1 中往下执行,执行 right = merge_sort([77, 31, 44, 55, 20]),整个过程类似于 Step 1 -- Step 14,就不赘述了

压力测试:

from timeit import timeit

def test():
    # import random
    # gen = (random.randint(1, 100) for i in range(100))  # 产生100个 1-99 范围内的随机整数
    # L = list(gen)
    L = [96, 2, 65, 23, 47, 58, 8, 48, 69, 92, 34, 83, 93, 47, 45, 55, 95, 15, 92, 24, 64, 19, 29, 55, 35, 48, 39, 29, 63, 94, 99, 38, 50, 10, 10, 93, 74, 27, 74, 44, 29, 81, 85, 86, 74, 30, 50, 50, 12, 12, 38, 75, 41, 87, 80, 97, 16, 48, 65, 69, 83, 71, 28, 9, 64, 69, 27, 74, 74, 86, 40, 69, 79, 79, 77, 100, 53, 72, 77, 16, 8, 36, 41, 58, 59, 29, 46, 79, 81, 66, 8, 35, 60, 52, 2, 82, 2, 36, 79, 66]
    merge_sort(L)

def merge_sort(L):
    n = len(L)
    if n <= 1:
        return L

    mid = n // 2
    left = merge_sort(L[:mid])
    right = merge_sort(L[mid:])

    return merge(left, right)

def merge(left, right):
    merged, left_index, right_index = [], 0, 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1
    return merged + left[left_index:] + right[right_index:]


print('Merge sort function run 1000 times, cost: ', timeit('test()', 'from __main__ import test', number=1000), 'seconds.')


# Output:
Merge sort function run 1000 times, cost:  0.5221137649991934 seconds.

2.2 迭代法 - 自底向上(Bottom Up)

from collections import deque


def merge_sort(L):
    n = len(L)
    # size表示要进行归并操作的左右子序列的长度,取值范围为1, 2, 4 ... n-1
    size = 1  # 当 size = 1 时,左右子序列都是单个元素,肯定为有序的,可以直接归并操作了
    while size < n:  # size最大值为 n - 1; 如果size < n-1,则序列为奇数个数时,最后一个元素不会被排序,是错误的
        '''提供 left 和 right 两个子序列给 merge(left, right) 函数即可'''
        # low, mid, high 都表示下标
        low = 0
        while low + size < n:  # 保证 mid = low + size 不会下标越界
            mid = low + size
            high = mid + size  # 即 high = low + 2 * size

            left = L[low:mid]
            right = L[mid:high]  # 切片不会取high,所以 high = low + 2 * size 也没事

            merged = merge(left, right)
            # 将归并操作排序好的序列,重新赋值给 L[low:high]
            L[low:high] = merged
            # 将下标 low 往右移动
            low = high
        # 自底向上,第1次归并操作是针对单个元素,结果为2个元素。第2次归并操作就是针对2个元素,结果为4个元素...
        size = 2 * size

    return L


def merge(left, right):
    '''归并操作,使用deque'''
    merged, left, right = [], deque(left), deque(right)

    while left and right:
        merged.append(left.popleft() if left[0] <= right[0] else right.popleft())  # deque popleft is also O(1)
    merged.extend(right if right else left)  # 如果 left序列 还有没比较的元素

    return merged


def is_sorted(L):
    '''辅助函数: 用来判断 '归并排序函数(merge_sort)' 的输出结果是否是正确的升序序列'''
    prev = L[0]
    for i in range(1, len(L)):
        if prev > L[i]:
            print('Sort ascending failed.')
            return False
        prev = L[i]
    print('Sort ascending succeed.')
    return True


if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    merged = merge_sort(L1)
    if is_sorted(merged):
        print('After: ', merged)

# Output:
Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
Sort ascending succeed.
After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

Merge Sort 02

过程分析:

Step 1: 对应上图中标号1,size = 1low = 0mid = 1high = 2,所以 left = L[0:1](即 [54]),right = L[1:2](即 [26])。进行第1次归并操作,结果为 [26, 54],修改原始序列的值,所以 L = [26, 54, 93, 17, 77, 31, 44, 55, 20]。然后修改 low = high = 2

Step 2: 对应上图中标号2,size = 1low = 2mid = 3high = 4,所以 left = L[2:3](即 [93]),right = L[3:4](即 [17])。进行第2次归并操作,结果为 [17, 93],修改原始序列的值,所以 L = [26, 54, 17, 93, 77, 31, 44, 55, 20]。然后修改 low = high = 4

Step 3: 对应上图中标号3,size = 1low = 4mid = 5high = 6,所以 left = L[4:5](即 [77]),right = L[5:6](即 [31])。进行第3次归并操作,结果为 [31, 77],修改原始序列的值,所以 L = [26, 54, 17, 93, 31, 77, 44, 55, 20]。然后修改 low = high = 6

Step 4: 对应上图中标号4,size = 1low = 6mid = 7high = 8,所以 left = L[6:7](即 [44]),right = L[7:8](即 [55])。进行第4次归并操作,结果为 [44, 55],修改原始序列的值,所以 L = [26, 54, 17, 93, 31, 77, 44, 55, 20]。然后修改 low = high = 8此时,low + size < n 条件为False,退出内层while循环。然后修改 size = 2 * size = 2

Step 5: 对应上图中标号5,size = 2low = 0mid = 2high = 4,所以 left = L[0:2](即 [26, 54]),right = L[2:4](即 [17, 93])。进行第5次归并操作,结果为 [17, 26, 54, 93],修改原始序列的值,所以 L = [17, 26, 54, 93, 31, 77, 44, 55, 20]。然后修改 low = high = 4

Step 6: 对应上图中标号6,size = 2low = 4mid = 6high = 8,所以 left = L[4:6](即 [31, 77]),right = L[6:8](即 [44, 55])。进行第6次归并操作,结果为 [31, 44, 55, 77],修改原始序列的值,所以 L = [17, 26, 54, 93, 31, 44, 55, 77, 20]。然后修改 low = high = 8此时,low + size < n 条件为False,退出内层while循环。然后修改 size = 2 * size = 4

Step 7: 对应上图中标号7,size = 4low = 0mid = 4high = 8,所以 left = L[0:4](即 [17, 26, 54, 93]),right = L[4:8](即 [31, 44, 55, 77])。进行第7次归并操作,结果为 [17, 26, 31, 44, 54, 55, 77, 93],修改原始序列的值,所以 L = [17, 26, 31, 44, 54, 55, 77, 93, 20]。然后修改 low = high = 8此时,low + size < n 条件为False,退出内层while循环。然后修改 size = 2 * size = 8

Step 8: 对应上图中标号8,size = 8low = 0mid = 8high = 16,所以 left = L[0:8](即 [17, 26, 31, 44, 54, 55, 77, 93]),right = L[8:16](即 [20],切片操作中 stop 可以越界)。进行第8次归并操作,结果为 [17, 20, 26, 31, 44, 54, 55, 77, 93],修改原始序列的值,所以 L = [17, 20, 26, 31, 44, 54, 55, 77, 93]。然后修改 low = high = 16此时,low + size < n 条件为False,退出内层while循环。然后修改 size = 2 * size = 16,外层while循环的条件 size < n 也为False,退出外层while循环。执行 return L,整个归并排序函数结束!

压力测试:

from collections import deque
from timeit import timeit

def merge_sort():
    # import random
    # gen = (random.randint(1, 100) for i in range(100))  # 产生100个 1-99 范围内的随机整数
    # L = list(gen)
    L = [96, 2, 65, 23, 47, 58, 8, 48, 69, 92, 34, 83, 93, 47, 45, 55, 95, 15, 92, 24, 64, 19, 29, 55, 35, 48, 39, 29, 63, 94, 99, 38, 50, 10, 10, 93, 74, 27, 74, 44, 29, 81, 85, 86, 74, 30, 50, 50, 12, 12, 38, 75, 41, 87, 80, 97, 16, 48, 65, 69, 83, 71, 28, 9, 64, 69, 27, 74, 74, 86, 40, 69, 79, 79, 77, 100, 53, 72, 77, 16, 8, 36, 41, 58, 59, 29, 46, 79, 81, 66, 8, 35, 60, 52, 2, 82, 2, 36, 79, 66]

    n = len(L)
    size = 1
    while size < n:
        low = 0
        while low + size < n:
            mid = low + size
            high = mid + size

            left = L[low:mid]
            right = L[mid:high]

            merged = merge(left, right)
            L[low:high] = merged

            low = high

        size = 2 * size

    return L

def merge(left, right):
    merged, left, right = [], deque(left), deque(right)

    while left and right:
        merged.append(left.popleft() if left[0] <= right[0] else right.popleft())  # deque popleft is also O(1)
    merged.extend(right if right else left)

    return merged


print('Merge sort function run 1000 times, cost: ', timeit('merge_sort()', 'from __main__ import merge_sort', number=1000), 'seconds.')


# Output:
Merge sort function run 1000 times, cost:  0.5063995326536888 seconds.

3. 性能

3.1 时间复杂度

  • 最优时间复杂度: O(n log n)
  • 最坏时间复杂度: O(n log n) typical,O(n) natural variant
  • 平均时间复杂度: O(n log n)

3.2 空间复杂度

О(n) total with O(n) auxiliary, O(1) auxiliary with linked lists

3.3 稳定性

它是稳定的排序算法

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3排序算法05 - 归并排序

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录