''' 先递归分解数组,后合并数组 将数组分解最小之后,然后合并两个有序数组。 比较两个数组最前面的数,谁小就先取谁, 取了之后相应的指针就向后移一位,然后再比较,直到一个数组为空 最后把另一个数组的剩余部分添加过来 ''' def merge_sort(alist): if len(alist) <= 1: # 如果只有一个元素,则不需要进行排序,直接返回结果 return alist # 二分分解 num = len(alist)//2 left = merge_sort(alist[:num]) right = merge_sort(alist[num:]) # 合并 return merge(left,right) def merge(left, right): '''合并操作,将两个有序数组left[]和right[]合并成一个大的有序数组''' #left与right的下标指针 l, r = 0, 0 result = [] while l<len(left) and r<len(right): if left[l] < right[r]: # 当左面的第l个元素小于右面的第r元素时 result.append(left[l])#添加左面的第一个元素 l += 1#左面元素l +1 else: result.append(right[r])#如果不大于,右面元素r +1 r += 1 result += left[l:]#如果左面还有没进行比较的元素、则全部添加到比较后的result内部 result += right[r:] return result alist = [54,26,93,17,77,31,44,55,20] sorted_alist = merge_sort(alist) print(sorted_alist)
2020-05-07