歸并排序的含義就是將兩個或兩個以上的有序數(shù)據(jù)序列合并成一個新的有序數(shù)據(jù)序列。它的基本思想就是假設(shè)數(shù)組A有N個元素，那么可以看成數(shù)組A是又N個有序的子序列組成，每個子序列的長度為1，然后再兩兩合并，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合并，如此重復(fù)，值得得到一個長度為N的有序數(shù)據(jù)序列為止，這種排序方法也稱為2—路合并排序。
1
#include <stdio.h>
2#include <cstdlib>
3
4#define TOTAL_NUM 1000
5#define MAX_NUM 200
6
7int merge(int sort[],int iLit,int iMid,int iHig)
8
{
9
int n1 = iMid-iLit+1;
10 int n2 = iHig-iMid;
11 int *L = (int*)malloc((n1+2)*sizeof(int));
12 int *R = (int*)malloc((n2+2)*sizeof(int));
13
14 int i=0;
15 for (i=1;i<=n1;i++)
16
{
17 L[i] = sort[iLit+i-1];
18
}
19 int j=0;
20 for (j=1;j<=n2;j++)
21 {
22 R[j] = sort[iMid+j];
23 }
24 L[n1+1] = R[n2+1] = RAND_MAX;
25 i=j=1;
26 int k=0;
27 for (k=iLit;k<=iHig;k++)
28 {
29 if (L[i]<=R[j])
30 {
31 sort[k] = L[i];
32 i++;
33 }else
34 {
35 sort[k] = R[j];
36 j++;
37 }
38 }
39 free(L);
40 free(R);
41 return 0;
42
}
43
44void SORT(int sort[],int iLit,int iHig)
45{
46 int iMid = 0;
47 if (iLit<iHig)
48 {
49 iMid = (iLit+iHig)/2;
50 SORT(sort,iLit,iMid);
51 SORT(sort,iMid+1,iHig);
52 merge(sort,iLit,iMid,iHig);
53 }
54}
55
56int main(int argc,char* argv[])
57{
58 int Sort[TOTAL_NUM];
59
60 int iPrintCount = 0;
61 int i = 0;
62 printf("::: old order ::: \n");
63 for (i=0;i<TOTAL_NUM;i++)
64 {
65 Sort[i] = (rand()+MAX_NUM)%MAX_NUM;
66 printf("%5ld ",Sort[i]);
67 if(++iPrintCount==10)
68 {
69 iPrintCount = 0;
70 printf("\n");
71 }
72 }
73
74 //merge sort
75 SORT(Sort,0,TOTAL_NUM-1);
76
77 iPrintCount = 0;
78 printf("\n::: new order ::: \n");
79 for (i=0;i<TOTAL_NUM;i++)
80 {
81 printf("%5ld ",Sort[i]);
82 if(++iPrintCount==10)
83 {
84 iPrintCount = 0;
85 printf("\n");
86 }
87 }
88
89 getchar();
90 return 0;
91}