归并排序与堆排序

 1 #include <iostream>
 2 using namespace std;
 3 
 4 //  归并排序
 5 void Merge(int a[],int b[],int i,int m,int n)
 6 {
 7     int j,k;
 8     for(j = m+1,k=i;i<=m&&j<=n;k++)
 9     {
10         if(a[i] < a[j]) 
11             b[k] = a[i++];
12         else 
13             b[k] = a[j++];
14     }
15 
16     if(i<=m) 
17         for(int p=i;p<=m;p++,k++) b[k] = a[p];
18     if(j<=n) 
19         for(int p=j;p<=n;p++,k++) b[k] = a[p];
20 }
21 
22 void copyArray(int a[],int b[],int s,int e)
23 {
24     for(int i = s;i<=e;i++)
25          b[i] = a[i];
26 }
27 void Merge_Sort(int a[],int b[],int s,int t)
28 {
29     if(s == t) b[s] = a[s];
30     else{
31         int m = (s + t)/2;
32         Merge_Sort(a,b,s,m);
33         Merge_Sort(a,b,m+1,t);
34         Merge(b,a,s,m,t);  
35         copyArray(a,b,s,t); // 减少一个中间数组的空间开销
36     }
37 }
38 
39 void main()
40 {
41     int a[10] = {5,4,3,2,-1,9,10,15,8,6};
42     int b[10];
43     Merge_Sort(a,b,0,9);
44     for(int i=0;i<10;i++)
45         cout << a[i] << endl;
46 }

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 // 大顶堆排序
 5 
 6 void HeapAdjust(int a[],int p,int size)
 7 {
 8     int lchild = 2*p;
 9     int rchild = 2*p+1;
10     int max = p;
11     if(p<=size/2)
12     {
13         if(a[max] < a[lchild] && lchild <=size) 
14             max = lchild;
15         if(a[max] < a[rchild] && rchild <=size) 
16             max = rchild;
17         if(max != p)
18         {
19             swap(a[max],a[p]);
20             HeapAdjust(a,max,size);
21         }
22     }
23 }
24 
25 void HeapSort(int a[],int s,int size)
26 {
27     // 建堆
28     for(int i=size/2;i>=s;i--)
29         HeapAdjust(a,i,size);
30 
31     // 调整
32     for(int i=size;i>=s;i--)
33     {
34         swap(a[s],a[i]);
35         HeapAdjust(a,s,i-1);
36     }
37 }
38 
39 void main()
40 {
41     int a[]= {5,1,4,3,2,-1,9,10,-15,19,20};
42 
43     HeapSort(a,1,10);
44     for(int i=1;i<=10;i++)
45         cout << a[i] << endl;
46 }

与书上的代码有点差别，个人理解的差别吧...