排序算法之归并排序
一、原理
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。将已有序的子序列合并，得到完全有序的序列。如下图：
归并过程：
两个指针的元素比较大小，小的元素就会被放入临时列表中，最后的结果就是：
算法步骤：
（1）申请临时空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置，如上图的左侧2和右侧3的位置
（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
（4）重复步骤 3 直到某一指针达到序列尾；
（5）将另一序列剩下的所有元素直接复制到合并序列尾。
二、实现
针对任意个前后有序的序列，将其合并为整个有序的序列，可以实现的代码如下：
def merge(li,start,mid,last): """ :param li: 传入的序列 :param start: 序列第一个位置的索引 :param mid: 序列中间位置的索引 :param last: 序列最后一个元素的索引 :return: """ i=start #左边开始指针的位置 j=mid+1 #右边开始指针的位置 temp=[] #申请临时空间 while i<=mid and j<=last: #当两个指针都没有移动到序列尾部 if li[i]<li[j]: temp.append(li[i]) i+=1 else: temp.append(li[j]) j+=1 while i<=mid: #当右边的指针移动到尾部，将左侧的剩下元素全部拷贝到temp temp.append(li[i]) i+=1 while j<=last:#当左边的指针移动到尾部，将右侧的剩下元素全部拷贝到temp temp.append(li[j]) j+=1 li[start:last+1]=temp #将临时列表中的元素再赋给li列表，节约空间 li=[2,4,7,9,3,5,6,8] merge(li,0,3,7) print(li) #[2, 3, 4, 5, 6, 7, 8, 9]
上述算法进行的前提序列前后两段已经是有序的，对于任意一个序列如何使用这种算法呢？使用先分解后归并的思想。
- 分解：将序列越分越小，直至分成一个元素。
- 终止条件：一个元素是有序的。
- 归并：将两个有序序表进行合成一个有序序列。
实现代码：
def merge(li,start,mid,last): """ :param li: 传入的序列 :param start: 序列第一个位置的索引 :param mid: 序列中间位置的索引 :param last: 序列最后一个元素的索引 :return: """ i=start #左边开始指针的位置 j=mid+1 #右边开始指针的位置 temp=[] #申请临时空间 while i<=mid and j<=last: #当两个指针都没有移动到序列尾部 if li[i]<li[j]: temp.append(li[i]) i+=1 else: temp.append(li[j]) j+=1 while i<=mid: #当右边的指针移动到尾部，将左侧的剩下元素全部拷贝到temp temp.append(li[i]) i+=1 while j<=last:#当左边的指针移动到尾部，将右侧的剩下元素全部拷贝到temp temp.append(li[j]) j+=1 li[start:last+1]=temp #将临时列表中的元素再赋给li列表，节约空间 def mergeSort(li,start,last): if start<last: #至少两个元素，一个元素是有序的 mid=(start+last)//2 #取整 mergeSort(li,start,mid) #对左侧元素进行分解，当进行分解到一个元素时，不满足 start<last，退出递归函数，执行 merge(li,start,mid,last)，就会将左侧排序好 mergeSort(li,mid+1,last) merge(li,start,mid,last) li=[6,2,1,8,0,9,5] mergeSort(li,0,len(li)-1) print(li)#[0, 1, 2, 5, 6, 8, 9]