【重温经典算法之一】归并排序

归并排序的基本思想是分治法，先将要排序的数组从中间分成两个小的数组，然后分别排序这两个小的数组，最后将这两个小的已经排序的数组合并成一个有序的数组。所以归并排序的基本框架为：

 1 MergeSort(array, start, end)
 2 {
 3 　　　if (start < end)
 4 　　　{
 5 　　　    mid = (start + end) / 2;
 6 　　　    MergeSort(array, start, mid);  //递归排序左边的数组
 7 　　　    MergeSort(array, mid + 1, end);  //递归排序右边的数组
 8 　　　    MergeArray(array, start, mid, end);  //合并两个已经排序的相邻数组
 9 　　　}
10 }

有了上面的框架，归并排序就转换为将两个已经排序的数组合并为一个大的排序数组问题。这个非常简单，只要先比较二个数组的第一个数，谁小就先取谁，取了后就在对应数组中删除这个数。然后再进行比较，如果有数组为空，那直接将另一个数组的数据依次取出即可。

 1 void MergeArray(int data[], int start, int mid, int end, int temp[])
 2 {
 3     int i = start, j = mid + 1, k = start;
 4 
 5     while (i <= mid && j <= end)
 6     {
 7         if (data[i] <= data[j])
 8             temp[k++] = data[i++];
 9         else
10             temp[k++] = data[j++];
11     } 
12     while (i <= mid)
13         temp[k++] = data[i++];
14     while (j <= end)
15         temp[k++] = data[j++];
16     for (k = start; k <= end; k++)
17         data[k] = temp[k];
18 }

归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在复杂度为O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）中效率算是比较高的。

 1 void MergeArray(int data[], int start, int mid, int end, int temp[])
 2 {
 3     int i = start, j = mid + 1, k = start;
 4 
 5     while (i <= mid && j <= end)
 6     {
 7         if (data[i] <= data[j])
 8             temp[k++] = data[i++];
 9         else
10             temp[k++] = data[j++];
11     } 
12     while (i <= mid)
13         temp[k++] = data[i++];
14     while (j <= end)
15         temp[k++] = data[j++];
16     for (k = start; k <= end; k++)
17         data[k] = temp[k];
18 }
19 void MergeSortRecursively(int data[], int start, int end, int temp[])
20 {
21     if (start == end)
22         return;
23 
24     int mid = (start + end) / 2;
25     MergeSortRecursively(data, start, mid, temp); //左边的排序
26     MergeSortRecursively(data, mid + 1, end, temp);  //右边的排序
27     MergeArray(data, start, mid, end, temp);
28 }
29 void MergeSort(int data[], int n)
30 {
31     if (data == NULL || n < 2)
32         return;
33     int *temp = new int[n];
34     MergeSortRecursively(data, 0, n - 1, temp);
35     delete [] temp;
36 }

View Code

　　下面是我在自己电脑上测试了下归并排序和qsort排序的效率：

　　对20000个随机数据进行测试：

　　对200000个随机数据进行测试：