今天写写归并排序，其实之前做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 阅读(255)
评论(0) 编辑 收藏 引用 所属分类:
杂