归并排序

 1 #include<iostream>
 2 
 3 #define SIZE 10
 4 
 5 using namespace std;
 6 
 7 //合并数组的前半部分和后半部分， 前提就是前后两个子数组分别都已经排好序了
 8  void mergeArray(int a[], int first, int mid, int last) 
 9  {
10      int i, j, m, n;
11      i = first, m = mid;
12      j = mid+1, n = last;
13      int k = 0;
14      int temp[SIZE];
15   
16      while(i<=m && j<=n) 
17      {
18          if(a[i] < a[j]) 
19          {
20              temp[k++] = a[i++];
21          }
22 
23          else 
24          {
25              temp[k++] = a[j++];
26          }
27       }
28 
29      //跳出循环说明数组的前半部分或者后半部分至少有一个已经被按顺序存入temp[]当中了
30      while(i<=m) temp[k++] = a[i++];
31      while(j<=n) temp[k++] = a[j++];
32  
33      for(i=0; i<k; i++) 
34      {
35          a[first+i] = temp[i];
36      }
37  }
38 
39 
40  //归并排序
41  void merge_sort(int a[], int start, int end)
42  {
43      int mid = (start+end)/2;
44      if(start<end)
45      {
46          merge_sort(a, start, mid);
47          merge_sort(a, mid+1, end);
48          mergeArray(a, start, mid, end);
49      }
50  }
51 
52 
53 int main() 
54 {
55     int a[SIZE];
56     int i;
57 
58     cout<<"Please input the num:"<<endl;
59     for(i=0; i<SIZE; i++)
60     {
61         cin>>a[i];
62     }
63 
64     cout<<"before the sort:"<<endl;
65     for(i=0; i<SIZE; i++)
66     {
67         cout<<a[i]<<" ";
68     }
69     cout<<endl;
70  
71     merge_sort(a, 0, SIZE-1);//归并排序
72 
73     cout<<"after the sort:"<<endl;
74     for(i=0; i<SIZE; i++)
75     {
76         cout<<a[i]<<" ";
77     }
78     cout<<endl;
79 }