归并排序

简单介绍

归并排序(英语:Merge sort,或mergesort),是建立在归并操作上的一种有效的排序算法,效率為 {\displaystyle O(n\log n)} {\displaystyle O(n\log n)}(大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。维基百科

动图解释

归并排序

代码实现

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
Desc:

        归并排序,便于理解print了很多步骤,
    看着麻烦可以删除。

"""

i = 0


def merge_sort(_list):

    global i

    list_length = len(_list)

    if list_length == 1:

        return _list

    mid = list_length // 2

    print("{} 正在排序的列表: {}\n".format(i, _list))

    i += 1

    # 这里不断递归
    left_sorted_list = merge_sort(_list[:mid])

    print("左侧:{}".format(left_sorted_list))

    # 左侧列表完成后继续递归处理右侧列表
    right_sorted_list = merge_sort(_list[mid:])

    print("右侧:{}".format(right_sorted_list))

    result = merge(left_sorted_list, right_sorted_list)

    print(">>> 已经完成排序:{}\n".format(result))

    return result


def merge(left_list, right_list):

    left, right = 0, 0

    merge_result = list()

    left_length = len(left_list)

    right_length = len(right_list)

    while left < left_length and right < right_length:

        if left_list[left] <= right_list[right]:

            merge_result.append(left_list[left])

            left += 1

        else:

            merge_result.append(right_list[right])

            right += 1

    merge_result += left_list[left:]

    merge_result += right_list[right:]

    return merge_result


if __name__ == '__main__':
    _list = [54, 26, 93, 17, 77, 31, 44, 55, 20]

    print("等待排序的列表: %s\n-----" % _list)

    sorted_alist = merge_sort(_list)

    print("-----\n排序完成的列表:%s" % sorted_alist)
最后修改:2021 年 03 月 16 日 05 : 22 PM
如果觉得我的文章对你有用,请随意赞赏