今天寫寫歸并排序，其實之前做oj題的時候已經寫過好幾次了，記得有道求逆序數的題就是用歸并排序做的，所以對它忘得還不算多，基本做法還是知道的，思想當然是二分，關鍵是merge的過程。
代碼貼一下，思想就不多說了，再說就說爛了～
1 /**********************************
2 * 將a[low] ~ a[mid] 和a[mid + 1] ~ a[high]
3 * 的元素進行合并
4 **********************************/
5 #define MAX 1000
6
7 void merge(int a[], int low, int mid, int high)
8 {
9 int b[MAX];
10 int i = low, j = mid, index = 0;
11
12 while (i < mid && j < high)
13 {
14 if (a[i] > a[j])
15 {
16 b[index++] = a[j++];
17 }
18 else
19 {
20 b[index++] = a[i++];
21 }
22 }
23
24 while (i < mid)
25 {
26 b[index++] = a[i++];
27 }
28
29 while (j < high)
30 {
31 b[index++] = a[j++];
32 }
33
34 memcpy(a + low, b, sizeof(int) * index);
35 }
36
37 void msort(int a[], int low, int high)
38 {
39 if (low == high - 1)
40 {
41 return;
42 }
43 else
44 {
45 int mid = (high + low) / 2;
46 msort(a, low, mid);
47 msort(a, mid, high);
48 merge(a, low, mid, high);
49 }
50 }
51
52 void merge_sort(int a[], int n)
53 {
54 msort(a, 1, n);
55 }
posted on 2011-05-01 22:00
myjfm 閱讀(292)
評論(0) 編輯 收藏 引用 所屬分類:
雜