排序算法之归并算法(Merge Sort)
归并排序算法
1.算法原理
归并排序就是将两个（或者两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的，
然后再把有序的子序列合并为整体有序序列。
初始数列为：A[0],A[1],...,A[n-1]
算法实现的步骤如下：
1) 把0~n-1的数组分为左数组A[0,...,n/2]和右数组A[n/2 + 1,..., n-1];
2) 对左数组和右数组进行迭代排序
3) 将排好序的左数组和右数组进行合并，那么最后的整个数组就是有序的数组序列。
示意图如下：
2. 源代码实现
#include <stdio.h>#include <stdlib.h>void merge(int A[], int low, int mid, int high){int length = high - low + 1;int *pData = NULL;int left = low;int right = mid + 1;int all = 0;//分配空间给pData；pData = (int*)malloc(sizeof(int) * length);//assert(NULL != pData);memset(pData, 0, length);//把排好序的左数组和右数组合并后放入pData中；while(left <= mid && right <= high){if(A[left] <= A[right]){pData[all] = A[left];left++;all++;}else{pData[all] = A[right];right++;all++;}}//移动剩下的数据if(left <= mid){memmove(&pData[all], &A[left], sizeof(int) * (mid - left + 1));}if(right <= high){memmove(&pData[all], &A[right], sizeof(int) * (high - right + 1));}//把排好序的数列移动到原始数组中memmove(&A[low], pData, sizeof(int) * (high - low + 1));free(pData);}void _merge_sort(int A[], int low, int high){int mid = 0;if(low < high){mid = low + (high -low) / 2;_merge_sort(A, low, mid);_merge_sort(A, mid + 1, high);merge(A, low, mid, high);}}void merge_sort(int A[], int length){_merge_sort(A, 0, length - 1);}void print_result(int A[], int length) { int i; for(i = 0; i < length; i++) { printf("%d\n", A[i]); } } int main() { int A[] = {49 ,38, 65, 97, 76, 13, 27}; int length = 7; printf("The initial A is:\n"); print_result(A, length); printf("The sorted A is:\n"); merge_sort(A, length); print_result(A, length); system("pause"); return 0; }
3.总结
归并排序算法可选择用于各种场合，
稳定的排序。即相等的元素的顺序不会改变
时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。
空间复杂度为 O(n) 。
比较操作的次数介于(nlogn) / 2和nlogn - n + 1。
赋值操作的次数是(2nlogn)
归并排序比较占用内存，但却效率高且稳定的算法。
引自http://baike.baidu.com/view/19000.htm