经典算法回顾之归并排序

浏览数：27 / 时间：2015年06月08日

　　归并排序是将两个或两个以上的有序子表合并成一个新的有序表。它的基本思想是分治法。对于二路归并而言，初始时将含有n个节点的待排序序列看作由n个长度为1的有序子表组成，将它们一次两两归并得到长度为2的若干有序自编，再对它们两两合并，知道得到长度为n的有序表，排序结束。

　　与快速排序和堆排序相比，归并排序的最大特点是，它是一种稳定的排序。归并排序可用顺序存储结构，也易于在链表上实现。对长度为n的文件，需进行log2n趟归并排序，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况还是在最坏情况下，均是O(nlog2n)。归并排序需要一个辅助空间来暂存两个有序子文件归并的结果，故其辅助空间空间复杂度为O(n)，显然它不是就地排序。

归并排序的基本架构为：

 1 MergeSort(int array[], int start, int 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 #include "stdafx.h"
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 void MergeOrderedArray(int data[], int start, int mid, int end ,int temp[])
 7 {//合并有序数组：其实合并的是[start,mid]和[mid+1,end]
 8     int i = start, j = mid +1, pTemp = start;
 9 
10     while(i <= mid && j <= end)
11     {
12         if(data[i] <= data[j])
13             temp[pTemp++] = data[i++];
14         else
15             temp[pTemp++] = data[j++];
16     }
17     while(i <= mid)//非空
18         temp[pTemp++] = data[i++];
19     while(j <= end)
20         temp[pTemp++] = data[j++];
21     for(pTemp = start; pTemp <= end; pTemp++)
22         data[pTemp]= temp[pTemp];//将辅助数组数据写回原数组
23 }
24 
25 void MergeSortRecursively(int data[], int start, int end,int temp[])
26 {//对数组data中范围在[start, end]中的数据进行归并排序
27     if(start >=0 && start < end)
28     {
29         int mid = (start + end)/2;
30         MergeSortRecursively(data, start, mid,temp);//递归排序左边的数组
31         MergeSortRecursively(data, mid+1, end,temp);//递归排序右边的数组
32         MergeOrderedArray(data, start, mid, end,temp);//合并两个已经排序的相邻数组
33     }
34 }
35 
36 void MergeSort(int data[] ,int size)
37 {
38     if(data == NULL || size < 2)
39         return;
40     int *temp = new int[size];//创建辅助空间
41     MergeSortRecursively(data, 0 ,size-1, temp);
42     delete[] temp;
43 }
44 int  main()
45 {
46     int unsorted[] = {3,6,1,4,5};
47     int length = sizeof(unsorted)/sizeof(int);
48 
49     for(int i=0;i<length;++i)
50        cout<<unsorted[i]<<" ";
51     cout<<endl;
52 
53     MergeSort(unsorted,length);
54 
55     for(int i=0;i<length;++i)
56         cout<<unsorted[i]<<" ";
57     cout<<endl;
58 
59     return 0;
60 }