归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
#include <stdio.h> #include <stdlib.h> /* 归并排序 mergeSort 说明：mergeSort需要借助一个O(n)大小的空间存储排序数组， */ void merge(int *a,int first,int mid,int last,int *p) { int i = first,j=mid+1; int k = first; while(i<=mid&&j<=last) { if(a[i]<a[j])p[k] = a[i++]; else p[k]=a[j++]; k++; } while(i<=mid)p[k++] = a[i++]; while(j<=last)p[k++] = a[j++]; for (int i = first; i <= last; i++) { a[i] = p[i]; } } void mergeSort(int *a,int first,int last,int *p) { if(first < last) { int mid = (last+first)/2; mergeSort(a,first,mid,p); mergeSort(a,mid+1,last,p); merge(a,first,mid,last,p); } } int main(int argc, char **argv) { int a[] = {2,24,3,19,45,12,1,66,34,7}; int size; int i; size = sizeof(a)/sizeof(int); int *p = (int*)malloc(sizeof(int)*(size+1)); mergeSort(a,0,size-1,p); for(i = 0; i < size; i++) { printf("%d ",a[i]); } printf("\n"); free(p); return 0; }
本文转自NewPanderKing51CTO博客，原文链接：http://www.cnblogs.com/newpanderking/p/3946791.html，如需转载请自行联系原作者
