归并排序

 1 #include "stdafx.h"
 2 
 3 //t[]在外部申请，以此避免在函数体内部反复申请数组的开销。
 4 void merge_array(int a[], int left, int middle, int right, int t[]) 
 5 {
 6     int l = left, r = middle + 1, k = 0;
 7     while(l <= middle && r <= right)
 8     {
 9         if(a[l] < a[r])
10              t[k++] = a[l++];
11         else
12             t[k++] = a[r++];
13     }
14 
15     while(l <= middle)
16         t[k++] = a[l++];
17 
18     while(r <= right)
19         t[k++] = a[r++];
20 
21     for(int i = 0; i < k; ++i)
22         a[left + i] = t[i];       //mark!第一次忘记写left了。
23 }
24 
25 void merge_sort(int a[], int left, int right, int t[])
26 {
27     if(left >= right) return;
28     int middle = (left + right)/2;
29     merge_sort(a, left, middle, t);
30     merge_sort(a, middle + 1, right, t);
31     merge_array(a, left, middle, right, t);    
32 }
33 
34 int _tmain(int argc, _TCHAR* argv[])
35 {
36     int array[] = {7,10,19,25,12,17,21,30,48};
37     
38     int * t = new int[sizeof(array)/sizeof(int)];    
39     merge_sort(array, 0, sizeof(array)/sizeof(int) - 1, t);
40     delete []t;
41 
42     getchar();
43     return 0;
44 }