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