[原]11-Python3实用教程-排序算法-归并排序

归并排序

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  • 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
  • 自下而上的迭代;

需要2倍于排序列表的额外空间

对于一个长度为N的列表,排序步骤:

1、先将列表一分二,二分四,四分八,一直分到所有拆分后的列表长度是1,不能再分了(分)

2、自下而上比较大小合并,八合成四,四合成二,二合成一,排序完成(治)

如下图(网上借鉴)

分治法

代码实现:

def sort(list):
    import math
    if(len(list)<2):
        return list
    middle = math.floor(len(list)/2)
    left, right = list[0:middle], list[middle:]
    return merge(sort(left), sort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

seq_list = [8, 6, 4, 9, 7, 3, 2, -4, 0, -100, 99]

print(sort(seq_list))
#[-100, -4, 0, 2, 3, 4, 6, 7, 8, 9, 99]
分享 提问
comments powered by Disqus