基本思想
归并排序（merge-sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案合并在一起，即分而治之)。
分治类似于二分的思想，打个不恰当的比喻，我们知道常见的冒泡，简单插入排序的时间复杂度都是O(n2)O(n^2)O(n2)，并且如果原数组的有序程度越高，这些简单排序的实际时间复杂度就会越小。对于一个长度为nnn的无序数组，如果一分为二成两个子数组，对每个子数组排序，那么时间为O((n/2)2)=O(n2/4)O((n/2)^2)=O(n^2/4)O((n/2)2)=O(n2/4)，然后由于子数组有序那么合并的时间也不需要很长，因此总体来讲分治的思想就能降低时间复杂度。
如下：
将数组切分成至多两个元素的一个个子数组，对每个子数组比较排序之后然后与依次合并，这样的形式也很像完全二叉树，下面是针对一个任意无序数组的动图演示。
项目方法
ir43Q0wJUO8030
y4zDL2006.02.06 15-30-42
EV50I
今日头条0iw642006-10-18 05:28:45
rU091XhUG89702
代码
# python3def mergesort(seq): """归并排序""" if len(seq) <= 1: return seq mid = len(seq) / 2 # 将列表分成更小的两个列表 # 分别对左右两个列表进行处理，分别返回两个排序好的列表 left = mergesort(seq[:mid]) right = mergesort(seq[mid:]) # 对排序好的两个列表合并，产生一个新的排序好的列表 return merge(left, right)def merge(left, right): """合并两个已排序好的列表，产生一个新的已排序好的列表""" result = [] # 新的已排序好的列表 i = 0 # 下标 j = 0 # 对两个列表中的元素 两两对比。 # 将最小的元素，放到result中，并对当前列表下标加1 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result += left[i:] result += right[j:] return resultseq = [5,3,0,6,1,4]print('排序前：',seq)result = mergesort(seq)print('排序后：',result)
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
