算法入门(算法导论第二章)

时间：2010-11-14 来源：Ray Z

Merge Sort 1 void merge(int data[], int p, int q, int r)
2 {
3     int i, j, k, n1, n2;
4     n1 = q - p + 1;
5     n2 = r - q;
6     int L[n1];
7     int R[n2];
8     for(i = 0, k = p; i < n1; i++, k++)
9         L[i] = data[k];
10     for(i = 0, k = q + 1; i < n2; i++, k++)
11         R[i] = data[k];
12     for(k = p, i = 0, j = 0; i < n1 && j < n2; k++)
13     {
14         if(L[i] > R[j])
15         {
16             data[k] = L[i];
17             i++;
18         }
19         else
20         {
21             data[k] = R[j];
22             j++;
23         }
24     }
25     if(i < n1)
26     {
27         for(j = i; j < n1; j++, k++)
28         data[k] = L[j];
29     }
30     if(j < n2)
31     {
32         for(i = j; i < n2; i++, k++)
33             data[k] = R[i];
34     }
35 }
36
37 void merge_sort(int data[], int p, int r)
38 {
39     if(p < r)
40     {
41         int q = (p + r) / 2;
42         merge_sort(data, p, q);
43         merge_sort(data, q + 1, r);
44         merge(data, p, q, r);
45     }
46 }

相关阅读更多 +