归并排序算法

归并排序算法。

归并排序法

归并排序算法,原理容易理解。但是到代码实现以及单步调试的时候,不是很明白了。
nlogn

当计算的值越大时,所需要的时间的比较。

把一个数组分成块,然后再进行分块,最后分成了一个一个的,然后再向上归并。

1 2 3 4 5 6 7 8
2 3 6 8 1 4 5 7
6 8 2 3 1 5 4 7
8 6 2 3 1 5 7 4

二分法,递归的方法

时间效率比空间效率重要。

两个已经排好序的元素数组,来比较数组头部的元素,谁更小,就放到头部。

i和j要比较的元素,k要放的位置,归并结束要放的最后一个元素的位置。

来自维基百科的图片讲解

拆分排序和合并排序

拆分

>>> a = range(1,10)
>>> a
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> len(a)
9
>>> mid = len(a) / 2
>>> mid
4
>>> a[:mid]
[1, 2, 3, 4]
>>> a[mid:]
[5, 6, 7, 8, 9]

拆分两部分之后,还需要继续拆分,直到不能再分为止。

#递归拆分
def split(lists):
    #递归退出条件
    length = len(lists)  #长度
    if length <= 1:
        return lists

    #取中间值
    mid = length // 2
    left = lists[:mid]
    right = lists[mid:]


    #递归拆分
    split(left)
    split(right)


if __name__ == '__main__':
    a = [3]
    print split(a)  

除了列表结果为1的时候,会返回结果,其他时候都返回None。拆分之后没有做后续处理,需要将拆分的列表合并和排序。

每次排序都是基于上次合并排序的结果。按照顺序抽取两个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

最终的代码:参考写出的。

# -*- coding:utf-8 -*-

def split(lists):
    #递归退出条件判断
    length = len(lists)
    if length <= 1:
        return lists

    #取整
    mid = length // 2 
    left = lists[:mid]
    right = lists[mid:]

    #递归拆分
    split(left)
    split(right)

    return merge(left,right)

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

    #递归拆分,取整
    mid = length // 2
    left = merge_sort(lists[:mid])
    right = merge_sort(lists[mid:])

    #合并排序
    return merge(left,right)

if __name__ == '__main__':
    a = [6,7,8,5,4,3,2,9,10,1]
    print '排序前',a

    print '排序后',merge_sort(a)

运行。

 C:\Users\Administrator\Desktop\Algo>python2 spitsort1.py
排序前 [6, 7, 8, 5, 4, 3, 2, 9, 10, 1]
排序后 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]   

合并和排序

# -*- coding:utf-8 -*-

def merge1(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

if __name__ == '__main__':
    a = [6,7,8,5,4]
    b = [3,2,9,10,1]
    print merge1(a,b)

结果

C:\Users\Administrator\Desktop\Algo>python2 merge.py
[3, 2, 6, 7, 8, 5, 4, 9, 10, 1]

把上面的函数简单合并一下。

# -*- 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 

    #递归拆分,取整
    mid = length // 2
    left = merge_sort(lists[:mid])
    right = merge_sort(lists[mid:])

    #归并排序
    return merge(left,right)

if __name__ == '__main__':
    a = [6,7,8,5,4,3,2,9,10,1]
    print '排序前',a

    print '排序后',merge_sort(a)    

结果

C:\Users\Administrator\Desktop\Algo>python2 splitsort2.py
排序前 [6, 7, 8, 5, 4, 3, 2, 9, 10, 1]
排序后 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
参考

归并排序

常见排序算法 - 归并排序 (Merge Sort)

Python实现归并排序算法