Python实现归并排序算法 归并排序1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。 分治法的基本思想 将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。 ###归并排序的基本思想 排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。 动画 代码实现 def merge(left, right): '''合并和排序''' i = 0 j = 0 result = [] length_left = len(left) length_right = len(right) while i < length_left and j < length_right: # 逐个比较两个列表的元素 # 小的添加进新列表,大的留下继续比较 if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 # 最后加上未比较的元素 result.extend(left[i:]) result.extend(right[j:]) return result def merge_sort(lists): '''归并排序入口,拆分列表''' # 递归退出条件判断 length = len(lists) if length <= 1: return lists # 递归拆分,取整,兼容py3 mid = length // 2 left = merge_sort(lists[:mid]) right = merge_sort(lists[mid:]) # 合并排序(归并排序) return merge(left, right)
numbers = [4, 0, 7, 9, 2, 8, 1, 3, 6, 5] assert merge_sort(numbers) == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
|