归并排序 MergeSort C语言实现

#include <stdlib.h> #include <stdio.h> void Merge(int *src, int *des, int begin, int mid, int end) { int i, j, k; for(j=mid+1, k=begin, i=begin; i<=mid && j<=end; k++) { if(src[i] < src[j]) des[k] = src[i++]; else des[k] = src[j++]; } //将未存储的数据存入des 因为未被比较的分组中数列一定是有序的 故依次存入 if(i <= mid) { for(; k<=end && i<=mid; i++, k++) { des[k] = src[i]; } } if(j <= end) { for(; k<=end && j<=end; j++, k++) { des[k] = src[j]; } } } void MSort(int *src, int *res, int begin, int end) { int temp[20] = {0}; //存储分组结果 int mid; if(begin == end) res[begin] = src[begin]; else { mid = (begin + end) / 2; MSort(src, temp, begin, mid); //将src[begin...mid]分组为有序temp[begin...mid] MSort(src, temp, mid+1, end); //将src[mid+1...end]分组为有序temp[mid+1...end] Merge(temp, res, begin, mid, end); //temp[begin...end]排序为有序res[beging...end] } } int main() { int i; int a[] = {32, 23, 2, 34, 1, 443, 4, 231}; int res[20] = {0}; MSort(a, res, 0, sizeof(a)/sizeof(int)-1); for(i=0; i<sizeof(a)/sizeof(int); i++) { printf("%d ", res[i]); } system("pause"); return 0; }