Divide-and-conquer思想在Merge Sort & quick sort的应用

Divide-and-conquer思想在Merge Sort & quick sort的应用

分而治之的思想指的是：

1. 把原问题（problem）拆分成一个个相似的小问题（subproblem），
2. 然后用同样的方法对这些小问题进行处理，
3. 最后再合并这些小问题的答案得到原问题的答案

一： 归并排序（merge sort）中运用了分而治之（divide-and-conquer）的思想.
举个例子：divide-and-conquer application to merge sorting:

图中的意思是: 原问题为： list0 = [b,f,h,a,d,k,g,j,e,c,i]
第一步：我们将problem，list0拆分成两个相同的subproblem，list1和list2: list1 = [b,f,h,a,d,k] & list2 = [g,j,e,c,i]
第二步：我们将两个subproblem solve independently得到： list1 = [a,b,d,f,h,k] & list2 = [c,e,g,j,i]
第三步：将subproblem的solution merge得到problem的solution：list0 = [a,b,c,d,e,f,g,h,I,j,k]

上面我们理解了分而治之的思想，以及在sorting的简单应用，下面我们介绍： merge sort的完整流程：

我们为了将原list进行sort，我们采用divide-and-conquer思想，将原list一直对半拆分成相似的subproblems直到list中只有一个元素，此时我们再反过来对subproblems的list单独solve，最后整合所有subproblems的结果得到原list的sort结果。

了解merge sort的流程后，我们看下merge sort的完整python实现代码：

解释其python的第一段代码：
为了solve subproblem，我们需要对两个无序的list sort为一个有序的list。所以我们需要先：res = ，给i,j 赋值为0，i为index of lst1,j为index of lst2.然后用lst1[i]与lst2[j]比较，小的那个元素就放入res[ ],以此类推。我们需要注意return的部分：
Return res + lst1[i:] + lst2[j:]是为了将lst1 or lst2中剩余的最后一个数值加进res[ ]

解释其python的第二段代码：
这段代码是从下到上整合

二：快速排序（quick sort）中也运用了分而治之（divide-and-conquer）的思想.

了解其原理：举个例子，原序列：15 22 13 27 12 10 20 25
Quick sort的关键词就是pivot（基准）。

1. 我们random select一个数作为 pivot，比如第一个数
2. 我们将比pivot小的数依次放pivot左边，大的放右边
3. 继续在pivot左右两边random select一个pivot，以此类推

Sample quick sort 的process：
Sample step1: 13 12 10 15 22 27 20 25
Sample step2: 12 10 13 15 20 22 27 25
Sample step3: 10 12 13 15 20 22 25 27
Sample step4: 10 12 13 15 20 22 25 27

完整代码：

作者：莫纳什大学本科精算和计算机科学双专业在读学生，教程参考学校lecture内容，希望大家对莫那什python基础课程感兴趣的可以和我一起讨论，微信号为unswkyle