归并排序算法(递归实现) flying0033

winston

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

　　将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

2. #ifndef MERGESORT_H
3. #define MERGESORT_H
4. #include <stdlib.h>
5. template<class T> inline void MergeSort(T *a,int len) //归并排序算法
6. {
7.         T *TR = (T *)malloc(sizeof(T) * len); //动态分配一个额外的存储空间
8.         MSort(a,TR,0,len-1); //分裂然后调用归并排序
9.         free(TR); //释放内存
10. }
11. template<class T> void Merge(T a[],T TR[],int low,int mid,int high) //归并排序
12. {
13.         int i = low;
14.         int j = mid + 1;
15.         int k = 0;
16.         while(i <= mid && j <= high)
17.         {
18.                 if(a[i] < a[j])  //进行排序存入动态分配的数组中
19.                         TR[k++] = a[i++];
20.                 else
21.                         TR[k++] = a[j++];
22.         }
23.         while(i <= mid) //如果前一半中还有未处理完的数据,按顺序移入动态分配的数组内
24.                 TR[k++] = a[i++];
25.         while(j <= high) //如果后一半中还有未处理完的数据，按顺序移入动态分配的数组内
26.                 TR[k++] = a[j++];
27.         for(int v = 0,i = low;i <= high;++v,++i) //将排序好的数据移回到原序列中
28.                 a[i] = TR[v];
29. }
30. template<class T> void MSort(T a[],T temp[],int low,int high)
31. {
32.         int mid;
33.         if(low < high)
34.         {
35.                 mid = (low + high) / 2; //进行分裂
36.                 MSort(a,temp,low,mid); //将前一半继续分裂
37.                 MSort(a,temp,mid + 1,high); //将后一半继续分裂
38.                 Merge(a,temp,low,mid,high); //进行归并排序
39.         }
40. }
41. #endif //MERGESORT_H
43. #include "MergeSort.h"
44. #include <stdio.h>
45. int main()
46. {
47.         int a[] = {20,19,35,33,17,42,15,55,9,5,8,3,1};
48.         int len = sizeof(a) / sizeof(*a);
49.         MergeSort(a,len);
50.         printf("排序后的数组序列:\n");
51.         for(int i = 0;i < len;++i)
52.                 printf("%d ",a[i]);
53.         printf("\n");
54.         return 0;
55. }

复制代码

作者：flying0033 发表于2011-12-16 10:22:45 原文链接