今天主要说一下归并排序，主要介绍可以看菜鸟教程的归并排序 归并排序的主要思路如下 1、将一个待排序列一分为2，得到左右两个待排子序列，如果序列长度小于2，就不再切分； 2、对得到的左右两个子序列重复步骤1； 3、对序列进行排序 图解如下（来源网络） 举个栗子 比如要排下面这个序

5,6,9,8,7

首先划分成如下样子

5,6 9,8,7

序列长度大于2，继续划分

5 || 6 9|| 8,7

我们发现，左子序列的子序列的长度都小于2，所以开始排序得到排序好的左子序列，右子序列的右子序列长度等于2，继续划分

5,6 9|| 8 || 7

对右子序列的子序列分别排序

5,6 9 || 7,8

然后再排序,此时左右子序列已经排序完成，

5,6 7,8,9

然后再排序得到完整的排序序列

5,6,7,8,9

具体代码如下

#数据的读取 x=input("请输入一个待排序列,中间用逗号分隔开\n") print(type(x)) x=x.replace(","," ").split() x=[int(val) for val in x] print(x) #归并排序算法 def mergeSort(arr): import math #输入一个序列，先划分成左右两个序列 if (len(arr)<2):#长度小于2就不用在分了 return arr middle=math.floor(len(arr)/2)#向下取整 left,right=arr[:middle],arr[middle:] return merge(mergeSort(left),mergeSort(right))#返回将两个序列排序后的序列 def merge(left,right): #这时候默认左右序列已经排好序，只需对他们再排序即可 result=[] while left and right:#两个序列中都有元素 if left[0]<=right[0]: result.append(left.pop(0)) else: result.append(right.pop(0)) while left: result.append(left.pop(0)) while right: result.append(right.pop(0)) return result y=mergeSort(x) print("y=",y)

结果

算法的稳定性

注意到我们在将排好序的左右子序列归并排序时，判断条件是左边序列的数等于右边的数时，先放入的是左边的数，这是就保持了相对位置不变，所以归并排序的算法是稳定的。