Python实现归并排序算法

  • 发布时间:2017年5月23日 17:15
  • 作者:杨仕航
  • 分类标签: Python
  • 阅读(2585)
  • 评论(1)

上次讲了最快的排序算法之一:快速排序算法。而快速排序不是一个稳定的算法,在交换过程中可能进入胡同一直在几个数字之间处理。这次将仔细讲解归并排序算法,一个稳定快速的排序算法。

归并排序采用分组处理,也是二分法的思想。将一组数据拆成两组,再将小组继续拆分为两个直到每个小组剩下1或0个元素。这时才开始对小组中的元素排序,排序完成之后再合并为新的小组。一直往上排序和合并直到排序完成。文字还是看不懂?或者我描述不清楚?看图,先是拆分,很明显的二分法思想:

20170523/20170523163508802.png


再拿最底层的数据开始合并和排序,如图一层层比较:

20170523/20170523163945289.png


这里需要思考两个东西:

1)如何拆分

2)如何合并且排序


先写拆分代码,根据列表长度使用切片器将其拆分成两半:

def split(lists):
    mid = len(lists) / 2
    left = lists[:mid]
    right = lists[mid:]


拆成两部分之后,还有继续拆分,直到剩下1或0个元素。这里可以采用递归:

def split(lists):
    # 递归退出条件判断
    length = len(lists)
    if length <= 1:
        return lists
        
    # 取整,兼容py3
    mid = length // 2
    left = lists[:mid]
    right = lists[mid:]
    
    # 递归拆分
    split(left)
    split(right)


这段代码不完善,除了列表长度小于等于1的时候,才返回结果。其他情况未返回结果,也就是说拆分之后就没有后续处理。这个地方留给排序代码,将拆分后的列表合并和排序。

那么合并排序的方法需要两个参数,两个list列表。由于我们每次排序都是基于上次合并排序后的结果。所以可以按照顺序抽取两个list的元素判断大小,并添加到新的列表中,完成合并排序的步骤。代码如下:

def merge(left, right):
    i = 0
    j = 0
    result = []
    length_left = len(left)
    length_right = len(right)
    
    while i < length_left and j < length_right:
        # 逐个比较两个列表的元素
        # 小的添加进新列表,大的留下继续比较
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            
    # 最后加上未比较的元素
    result.extend(left[i:])
    result.extend(right[j:])
    return result


再修改拆分的代码,加入合并排序的代码:

def split(lists):
    # 递归退出条件判断
    length = len(lists)
    if length <= 1:
        return lists
        
    # 递归拆分,取整,兼容py3
    mid = length // 2
    left = split(lists[:mid])
    right = split(lists[mid:])
    
    # 合并排序(归并排序)
    return merge(left, right)


可能有些人看不懂代码了,就加了一句合并排序的代码,就完成归并排序。

递归需要从最后面的步骤逆推,倒着想。当只有1个元素时返回lists拆分的结果,再两个1个元素的left和right列表合并排序。排序完成之后再返回一次合并排序后的列表。该返回结果是2个元素拆分之后的结果,再继续合并排序,继续返回结果给上一层。直到排序结束。完整代码如下,为了一目了然看出这是归并排序,修改方法名:

#coding:utf-8
def merge(left, right):
    '''合并和排序'''
    i = 0
    j = 0
    result = []
    length_left = len(left)
    length_right = len(right)
    
    while i < length_left and j < length_right:
        # 逐个比较两个列表的元素
        # 小的添加进新列表,大的留下继续比较
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            
    # 最后加上未比较的元素
    result.extend(left[i:])
    result.extend(right[j:])
    return result
    
def merge_sort(lists):
    '''归并排序入口,拆分列表'''
    # 递归退出条件判断
    length = len(lists)
    if length <= 1:
        return lists
        
    # 递归拆分,取整,兼容py3
    mid = length // 2
    left = merge_sort(lists[:mid])
    right = merge_sort(lists[mid:])
    
    # 合并排序(归并排序)
    return merge(left, right)


可用如下代码测试:

import random

lists = random.sample(range(2000000), 1000000)
result = merge_sort(lists)


使用random模块生成1百万个随机数进行归并排序。

在我的电脑测试大概耗时5、6秒,相对快速排序算法是慢了一点(快速排序耗时大概1、2秒),但它稳定。

上一篇:Django使用第三方存储服务器

下一篇:Python实现快速排序算法

评论列表

杨仕航

杨仕航

多谢网友“岁月神偷”,帮助找到文中纰漏的地方😁

2018-01-03 14:41 回复

新的评论

清空

猜你喜欢

  • 猜测中,请稍等...