归并排序

归并排序（Merge Sort）

  1.     归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法思路

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动画演示

9.5 归并排序 - 图1

代码实现

  1. def merge_sort(nums):
  2.     n = len(nums)
  3.     # 递归结束条件
  4.     if n <= 1:
  5.         return nums
  6.     # 分解问题，并递归调用
  7.     middle = len(nums) // 2
  8.     left = merge_sort(nums[:middle])
  9.     right = merge_sort(nums[middle:])
  11.     # 合并左右部分，完成排序
  12.     merged = []
  13.     while left and right:
  14.         if left[0] <= right[0]:
  15.             merged.append(left.pop(0))
  16.         else:
  17.             merged.append(right.pop(0))
  18.     merged.extend(right if right else left)
  19.     return merged
  21. print(merge_sort(nums=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]))
  1.     运行结果：
  1. [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  1.     排序过程：
  1. [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
  1. [3,44]—->[3,44]
  2. [38,5]—->[5,38]
  3. 合并：[3,5,38,44]
  4. [47,15]—->[15,47]
  5. [36,26]—->[26,36]
  6. 合并：[15,26,36,47]
  7. 合并：[3,5,15,26,36,38,44,47]
  8. [27,2]—->[2,27]
  9. [46,4]—->[4,46]
  10. 合并：[2,4,27,46]
  11. [19,50]—->[19,50]
  12. 合并：[19,48,50]
  13. 合并：[2,4,19,27,46,48,50]
  14. 合并：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

复杂度分析

  1.     时间复杂度分析：归并排序分为两个过程：分裂和归并。每次将数据平分成两份，直到不可再分为止，则共有logn层，而每一层的总份数由1增加到n。综合可知：共有logn层，每层的复杂度为O(n)，所以归并排序的时间复杂度为O(nlogn)。
  5.     空间复杂度：每次的分裂与合并都需要额外的空间来存储结果，但是在进行下一次的分裂与合并时会释放上一次使用的空间，这样可以使每次占用的空间就是数据的总个数n，所以归并排序的空间复杂度是O(n)。

优缺点

  1.         优点：归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。
  3.         缺点：代价是需要额外的内存空间。

性能改进

  1.     1.检测待归并的两个子数组是否已经有序;
  3.     2.通过再递归中交换参数来避免每次归并时都要复制数组到辅助数组。