常用排序算法之归并排序

时间：2010-10-07 来源：way_testlife

归并排序主要是指二路归并排序。

方法：设数组a中存放了n个数据元素，初始时把它们看成是n个长度为1的有序数组，然后从第一个子数组开始，把相邻的子数组两两合并，得到 n/2 的整数上界个长度为2的有序子数组（当n个奇数时，最后一个新的有序子数组的长度为1）；对于这些有序子数组再两两合并；如此重复，直到得到一个长度为n的有序数组为止。

C++实现：

一个二路归并排序可看成多个二路归并排序的合成：

Merge.cpp

 1 void Merge( DataType a[], int n, DataType swap[], int k )
 2 {
 3     int m = 0, u1, u2, i, j, l2;
 4     int l1 = 0;
 5 
 6     while ( l1 + k <= n -1 )
 7     {
 8         l2 = l1 + k;
 9         u1 = u2 - 1;
10         u2 = ( l2 + k - 1 <= n - 1)? l2 + k - 1: n - 1;
11 
12         //两个有序子数组的合并
13          for ( i = l1, j = l2; i <= u1 && j <= u2; m ++ )
14         {
15             if ( a[i].key <= a[j].key )
16             {
17                 swap[a] = a[i];
18                 i ++;
19             }
20             else
21             {
22                 swap[m] = a[j];
23                 j ++;
24             }
25         }
26 
27         //子数组2已归并完，将子数组1中剩余元素存放到数组swap中
28          while ( i <= u1 )
29         {
30             swap[m] = a[i];
31             m ++;
32             i ++;
33         }
34 
35         //子数组1已归并完，将子数组2中剩余元素存放到数组swap中
36          while( j <= u2 )
37         {
38             swap[m] = a[j];
39             m ++;
40             j ++
41         }
42 
43         l1 = u2 + 1;
44     }
45 
46     //将原始数组中只够一组的数据元素顺序存放到数组swap中
47      for ( i = l1; i < n; i ++, m ++)
48     {
49          swap[m] = a[i];
50     }
51 }

二路归并算法如下：

MergeSort.cpp

 1 void MergeSort( DataType a[], int n )
 2 {
 3     int i, k = 1;
 4     DataType *swap = new DataType[n];
 5 
 6     while ( k < n )
 7     {
 8         Merge(a, n, swap, k);
 9         for (i = 0; i < n; i ++)
10         {
11             a[i] = swap[i];
12         }
13         
14         k = 2 * k
15     }
16     
17     delete []swap;
18 }