归并排序算法基础 #
- 归并排序算法介绍
- 分治法算法介绍
- 分治法算法流程
收获 #
学完本节内容，可以初步理解并掌握归并排序算法。
归并排序算法介绍 #
归并排序(Merge Sort)是建立在归并操作上的一种效率很高的排序算法，比较占用内存。该算法是分治法(Divide and Conquer)的一个典型应用。
归并排序将两个或两个以上(一般是两个)有序的列表合并成一个新的有序列表。待排序列表是无序的，使用二分法递归地将列表最终拆分成只有一个元素的子表，只有一个元素的列表一定是有序的，此时递归往回合并，即可依次将待排序列表拆分然后合并成一个有序的列表。
分治法介绍 #
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。
求出子问题的解，就可得到原问题的解，是一种分目标完成程序算法，简单的问题可用二分法完成。
分治法算法流程 #
我们在使用分治算法求解问题的时候是把一个问题划分为多个小问题，然后通过各个小问题的答案来找到合适的，如果数据规模还是比较大，那么可以再进行一次分治算法，直到找到答案为止。
分治算法的解题步骤一般如下：
(1)分解，将要解决的问题划分成若干规模较小的同类问题；
(2)求解，当子问题划分得足够小时，用较简单的方法解决；
(3)合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
小结 #
理解归并排序的基础思想
理解分治法算法的求解过程
习题 #
- 习题1：描述归并排序算法所使用的的核心算法思想
- 习题2：尝试使用“分治法”思想对列表[10,17,50,7,30,15,5,38,21]中数字进行排序思路描述
