python 诠释 归并排序

归并排序 相对简单 归并的含义是将两个或两个以上有序表组合成一个新的有序表：

假设初始序列含有n个记录，则可看成是n个有序的子序列；每个子序列的长度为1，然后两两归并，得到 （n+1）/ 2 个子序列；再两两归并……如此重复，最终得到一个有序序列，这种叫做2路归并，如图所示：

 

代码实现：

 

def merge(list_a, list_b) :
    key_a,key_b = 0, 0
    result = []
    len_a = len(list_a)
    len_b = len(list_b)
    while key_a < len_a and key_b < len_b :
        if list_a[key_a] <= list_b[key_b] :
            result.append(list_a[key_a])
            key_a += 1
        else :
            result.append(list_b[key_b])
            key_b += 1
    while key_a < len_a :
        result.append(list_a[key_a])
        key_a += 1
    while key_b < len_b :
        result.append(list_b[key_b])
        key_b += 1
    return result 

#loop
def merge_sort1(list) :
    length = len(list)
    result = []
    step = 1
    while(step <= (length+1)/2) :
        result = []
        for i in range(0,length,step * 2) :
            max_key = i + 2*step
            result.extend(merge(list[i:i+step],list[i+step:i+step*2]))
        list = result
        step += 1
    return result

#recursion
def merge_sort2(list):
    length = len(list)
    if length == 1 :
        return list
    else : 
        temp_a = merge_sort2(list[0:length/2])
        temp_b = merge_sort2(list[length/2:length])
        return merge(temp_a,temp_b)

if __name__ == '__main__' : 
    list = [49,38,65,97,76,13,27]
    print merge_sort1(list)
    print merge_sort2(list)

 

其中 merge_sort1 采用循环的写法，merge_sort2 采用递归写法，与快速排序和堆排序相比，归并排序是一种稳定的排序方法

评论

1 楼 最佳蜗牛 2013-09-03  

很好，赞一个。