step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
step3 合并：将各个子问题的解合并为原问题的解。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
# -*- coding: utf-8 -*- """ @Time: 2018/4/11 @Author: songhao @微信公众号: zeropython @File: mergesort.py """ def 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 result += left[i:] result += right[j:] return result seq = [5,3,0,6,1,4] print('排序前：',seq) result = mergesort(seq) print('排序后：',result) |
支付宝扫一扫
