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 #loopdef 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#recursiondef 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 采用递归写法，与快速排序和堆排序相比，归并排序是一种稳定的排序方法