八大排序算法的Python实现__6__归并排序

环境

Python 3.5.2

原理

  • 将递归分解列表,直至最小(即每个列表仅有一个元素)
  • 将列表分解最小之后,递归合并两个列表,即挨个比较两个列表中最前面的元素,谁较小就将谁加入新的列表,而后该列表的下标后移一位,继续比较,直至其中一个列表为空,而后将另一个列表中剩余的元素加入新列表
  • 不断合并,直至完全排序完成

源码

def merge_sort(l):
    # 对列表进行二分分解
    n = len(l)
    if n <= 1:
        return l
    mid_posi = n//2
    # print(1)
    l_list = merge_sort(l[:mid_posi])
    # print(2)
    r_list = merge_sort(l[mid_posi:])
    # print(3)

    # 对列表进行合并
    sorted_list = []
    l_posi = 0
    r_posi = 0
    # print('l_list: %s' % l_list)
    # print('r_list: %s' % r_list)

    while l_posi < len(l_list) and r_posi < len(l_list):
        if l_list[l_posi] <= r_list[r_posi]:
            sorted_list.append(l_list[l_posi])
            l_posi += 1
        else:
            sorted_list.append(r_list[r_posi])
            r_posi += 1

    # 将列表剩余部分合并
    sorted_list += l_list[l_posi:]
    sorted_list += r_list[r_posi:]
    # print('sorted_list: %s' % sorted_list)

    return sorted_list


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

时间复杂度

  • 最优时间复杂度:O(nlogn)
  • 最坏时间复杂度:O(nlogn)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):稳定

说点什么

  Subscribe  
提醒