归并排序

浏览数：27 / 时间：2015年06月08日

今天对归并排序做个简短的总结，归并排序的思想是分治法的一种表现，因为可以用递归来解决对某一无序序列进行排序。

归并操作的思想大致分为以下几种步骤：

１，申请一块空间（抽象一点就是初始化一个数组）用来存放合并后的序列

２，设置两个指针（或下标），指向两个已经排序好的序列的首部，也就是下标为０指向第一个元素

３，把指针（或下标）对应的元素相比较，并且把小的放到第一部申请的空间的首处，并对相应的指针（或下标）＋１，也就是向后推移

４，重复步骤３直到指针（或下标）到达某一子序列的尾部

５，把剩余一个未完的子序列直接对接到归并好的序列的尾部

归并排序：

１，把一个含有n个元素的序列分一半出来，继续往下分，直到最后分成到只有单个元素，也就是含有n/2个序列

２，对相邻两个序列（第一次是单元素）进行比较，进行归并操作，变成２元素的序列

３，重复上述步骤，直到所有元素排序完毕

以下是python实现

 1 def MergeSort(lst):
 2     if len(lst) <= 1:
 3         return lst
 4     mid = int(len(lst)/2) #python2.7x不加int没问题
 5     ＃递归，相当于分到最后只剩下一个元素进行归并然后慢慢返回上一层最后完成所有工作
 6     return Merge(MergeSort(lst[:mid]), MergeSort(lst[mid:]))
 7 
 8 def Merge(L_lst, R_lst):
 9     result = []
10     #当两子序列都还有元素的时候，就进行归并操作
11     while L_lst and R_lst:
12         if L_lst <= R_lst:
13             result.append(L_lst.pop(0))
14         else:
15             result.append(R_lst.pop(0))
16     ＃当剩下左子序列有元素时，归并
17     while L_lst:
18         result.append(L_lst.pop(0))
19     ＃同上
20     while R_lst:
21         result.append(R_lst.pop(0))
22     return result
23 if __name__ == "__main__"":
24         
25     lst = [5,2,1,5,6,9,12]
26     print MergeSort(lst)