算法步骤：
1）将n个元素分成各含n/2个元素的子序列；
2）对两个子序列递归地排序；
3）合并两个以排序的子序列以得到排序结果。
最差时间复杂度 Θ(n logn )
最优时间复杂度 Θ(n )
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 6 void Merge(int nums[], int low, int mid, int high) { int *array = (int *)malloc((high-low+1) * sizeof(int));//用来存放合并后的序列 int begin1 = low; int end1 = mid; int begin2 = mid+1; int end2 = high; int i; //每次取两堆数中小的数 for(i = 0; begin1 <= end1 && begin2 <= end2; i++) { if(nums[begin1] <= nums[begin2]) array[i] = nums[begin1++]; else array[i] = nums[begin2++]; } //直接拷贝追加剩下那堆的所有数 if(begin1 <= end1) memcpy(array+i, nums+begin1, (end1-begin1+1) * sizeof(int)); if(begin2 <= end2) memcpy(array+i, nums+begin2, (end2-begin2+1) * sizeof(int)); //将排序好的序列拷贝回数组中 memcpy(nums+low, array, (high-low+1) * sizeof(int)); free(array); } void MergeSort(int nums[], int low, int high) { int mid = 0; if( low < high ) { mid = (low + high) / 2; MergeSort(nums, low, mid); MergeSort(nums, mid+1, high); Merge(nums, low, mid, high); } } int main() { int i = 0; int nums[N] = {14, 12, 15, 13, 11, 16}; MergeSort(nums, 0, N-1); for(i = 0; i < N; i++) printf("%d ", nums[i]); return 0; }
