Chapter14 Divide and Conquer

Presentation on theme: "Chapter14 Divide and Conquer"— Presentation transcript:

1 Chapter14 Divide and Conquer
分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。 小问题通常与原问题相似，可以递归地使用分而治之策略来解决。 2/22/2019

2 一个用分治法编写的过程通常包括以下几部分：基值处理部分，（即把问题分到足够小后要进行的处理），分解问题的部分，递归调用部分和合并处理部分。
由于分治策略是把问题分成较小的与原问题类型相同的子问题，对子问题的处理过程与对原问题的处理过程是相同的。所以，分治法处理问题的算法可以自然地写成一个递归的过程。 2/22/2019

3 找出伪币问题 一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。任务是找出这个伪造的硬币。
为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。 2/22/2019

4 金块问题 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。 2/22/2019

5 金块问题 2/22/2019

6 金块问题 用函数M a x（程序 ）通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。 设c(n)为使用分而治之方法所需要的比较次数。为了简便，假设n是2的幂。当n=2时，c(n) = 1。对于较大的n，c(n) = 2c(n/2) + 2。当n是2的幂时，使用迭代方法可知c(n) = 3n/2 - 2。 在本例中，使用分而治之方法比逐个比较的方法少用了25％的比较次数。 2/22/2019

7 归并排序 可以运用分而治之方法来解决排序问题，问题是将n 个元素排成非递减顺序。
2/22/2019

8 归并排序-1 假设仅将n个元素的集合分成两个子集合。现在需要确定如何进行子集合的划分。
一种可能性就是把前面n-1个元素放到第一个子集中（称为A），最后一个元素放到第二个子集里（称为B）。按照这种方式对A递归地进行排序。由于B仅含一个元素，所以它已经排序完毕，在A排完序后，只需要将A和B合并起来。 2/22/2019

9 归并排序-1 把这种排序算法与InsertionSort（见程序2-15）进行比较，可以发现这种排序算法实际上就是插入排序的递归算法。
2/22/2019

10 归并排序-2 把n个元素划分成两个子集合的另一种方法是将含有最大值的元素放入B，剩下的放入A中。然后A被递归排序。为了合并排序后的A和B，只需要将B添加到A中即可。 2/22/2019

11 归并排序-2 假如用函数Max来找出最大元素，这种排序算法实际上就是SelectionSort的递归算法。 2/22/2019

12 归并排序-3 假如用冒泡过程来寻找最大元素并把它移到最右边的位置，这种排序算法就是BubbleSort的递归算法。这两种递归排序算法的复杂性均为Θ(n2)。 若一旦发现A已经被排好序就终止对A进行递归分割，则算法的复杂性为O(n2) 2/22/2019

13 思考 采用平衡分割法? A集合中含有n/k 个元素，B中包含其余的元素。 2/22/2019

14 分而治之排序算法的伪代码 template<class T> void sort( T E, int n)
{ / /对E中的n 个元素进行排序， k为全局变量 if (n >= k) { i = n/k; j = n-i; 令A 包含E中的前i 个元素 令B 包含E中余下的j 个元素 sort( A , i ) ; sort( B , j ) ; merge(A,B,E,i,j,); //把A 和B 合并到E } else 使用插入排序算法对E 进行排序 2/22/2019

15 归并排序 k=2的排序方法被称为归并排序(merge sort)，或更精确地说是二路归并排序（two-way merge sort)。
2/22/2019

16 归并排序 归并排序的平均复杂性为Θ(nlogn)。 2/22/2019

17 二路归并排序-2 另一种二路归并排序算法是这样的：首先将每两个相邻的大小为1的子序列归并，然后对上一次归并所得到的大小为2的子序列进行相邻归并，如此反复，直至最后归并到一个序列，归并过程完成。 通过轮流地将元素从a 归并到b 并从b 归并到a，可以虚拟地消除复制过程。 2/22/2019

18 二路归并排序-2 template<class T> void MergeSort(T a[], int n)
{// 使用归并排序算法对a[0:n-1] 进行排序 T *b = new T [n]; int s = 1; // 段的大小 while (s < n) { MergePass(a, b, s, n); // 从a归并到b s += s; MergePass(b, a, s, n); // 从b 归并到a } 2/22/2019

19 MergePass函数 template<class T>
void MergePass(T x[], T y[], int s, int n) {// 归并大小为s的相邻段 int i = 0; while (i <= n - 2 * s) { // 归并两个大小为s的相邻段 Merge(x, y, i, i+s-1, i+2*s-1); i = i + 2 * s; } // 剩下不足2个元素 if (i + s < n) Merge(x, y, i, i+s-1, n-1); else for (int j = i; j <= n-1; j++) // 把最后一段复制到y y[j] = x[j]; 2/22/2019

20 Merge函数 template<class T>
void Merge(T c[], T d[], int l, int m, int r) {// 把c[l:m]] 和c[m:r] 归并到d [ l : r ] . int i = l, // 第一段的游标 j = m+1, // 第二段的游标 k = l; // 结果的游标 / /只要在段中存在i和j，则不断进行归并 while ((i <= m) && (j <= r)) if (c[i] <= c[j]) d[k++] = c[i++]; else d[k++] = c[j++]; // 考虑余下的部分 if (i > m) for (int q = j; q <= r; q++) d[k++] = c[q]; else for (int q = i; q <= m; q++) } 2/22/2019

21 归并排序 稳定排序？ 2/22/2019

22 快速排序 n 个元素被分成三段（组）：左段left，右段right和中段middle。中段仅包含一个元素。
左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此left和right中的元素可以独立排序，并且不必对left和right的排序结果进行合并。 middle中的元素被称为支点(pivot)。 2/22/2019

23 快速排序 C.R.A.Hoare于1962年提出。 一旦知道某元素比基准值小，它就不必再与那些大的元素比较。同样，大的元素也不必与小的再比较。 2/22/2019

24 快速排序伪代码 //使用快速排序方法对a[0:n-1]排序 从a[0:n-1]中选择一个元素作为middle，该元素为支点
把余下的元素分割为两段left和right，使得left中的元素都小于等于支点，而right中的元素都大于等于支点 递归地使用快速排序方法对left进行排序 递归地使用快速排序方法对right进行排序 所得结果为left+middle+right 2/22/2019

25 例 考察元素序列[4,8,3,7,1,5,6,2]。假设选择元素6作为支点，则6位于middle；4，3，1，5，2位于left；8，7位于right。当left排好序后，所得结果为1，2，3，4，5；当right排好序后，所得结果为7，8。把right中的元素放在支点元素之后，left中的元素放在支点元素之前，即可得到最终的结果[1,2,3,4,5,6,7,8]。 2/22/2019

26 快速排序 template<class T> void QuickSort(T *a,int n)
{//对a[0:n-1]进行快速排序 {//要求a[n]必需有最大关键值 quickSort(a,0,n-1);//支点在位置1 } 2/22/2019

27 快速排序 template<class T> void quickSort(T a[],int l,int r)
{//排序a[l:r]，a[r+1]有大值 if(l>=r)return; int i=l,//从左至右的游标 j=r+1;//从右到左的游标 T pivot=a[l];//支点 2/22/2019

28 快速排序 //把左侧>=pivot的元素与右侧<=pivot的元素进行交换 while(true){
do{//在左侧寻找>=pivot的元素 i=i+1; }while(a[i]<pivot); do{//在右侧寻找<=pivot的元素 j=j-1; }while(a[j]>pivot); if(i>=j)break;//未发现交换对象 Swap(a[i],a[j]); } 2/22/2019

29 快速排序 //设置pivot a[l]=a[j]; a[j]=pivot; quickSort(a,l,j-1);//对左段排序
quickSort(a,j+1,r);//对右段排序 } 2/22/2019

30 例 考察元素序列[4,8,3,7,1,5,6,2]。 2/22/2019

31 快速排序 快速排序的平均复杂性为Θ(nlogn)。 2/22/2019

32 快速排序 稳定排序？ 2/22/2019

33 2/22/2019

34 各排序算法平均时间的曲线图 2/22/2019