第二章归并排序分治法

分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

 1  
 2 #include "stdafx.h"
 3 #include<iostream>
 4 using namespace std;
 5  
 6 void Merge(int *arr,int p ,int q ,int r);//归并排序
 7  
 8 void mergesort(int *arr,int p,int r);
 9 void ViewData(int *,int len);
10 int _tmain(int argc, _TCHAR* argv[])
11 {
12 int arr[]={5,2,12,34,2,4,6,1};
13 mergesort(arr,0,7);
14 ViewData(arr,8);
15 return 0;
16 }
17  
18 void mergesort(int *arr,int p,int r)
19 {
20 if(p<r){    //如果p>=r,的话,说明..该子数组最多有一个元素，所以已经排好序了。所以这里只考虑p<r的时候.
21 int q=(p+r)/2;
22 mergesort(arr,p,q);
23 mergesort(arr,q+1,r);
24 Merge(arr,p,q,r);
25 }
26 }
27 //归并排序方法调用
28 void Merge(int *arr,int p ,int q ,int r)
29 {
30 int n1 = q-p+1;
31 int n2 = r-q;
32 int *a1=new int[n1];
33 int *a2=new int[n2];
34  
35 for(int i =0;i!=n1;++i)
36 {a1[i]=arr[p+i];}
37 for(int i =0;i!=n2;++i)
38 {a2[i]=arr[q+i+1];}
39 int m=0,j=0,k=0;
40 for(k = p;k<=r+1;k++)
41 {
42  
43 if(a1[m]<=a2[j])
44 {
45 arr[k]=a1[m];
46 m++;
47 }
48 else
49 {
50 arr[k]=a2[j];
51 j++;
52 }
53  
54 if(j==n2)
55 {
56 for(int tempi = m;tempi<n1;++tempi)
57 {
58 arr[++k]=a1[tempi];
59 }
60 break;
61 }
62  
63 if(m==n1)
64 {
65 for(int tempj = j;tempj<n2;++tempj)
66 {
67 arr[++k]=a2[tempj];
68 }
69 break;
70 }
71  
72 }
73  
74 }
75  
76 void ViewData(int *arr,int len)
77 {
78 for(int i =0;i!=len;i++)
79 {
80 cout<<arr[i]<<endl;
81 }
82 }
83

第二章 归并排序 分治法

第二章归并排序分治法