归并排序（递归和非递归方法实现）
/*归并排序VS2010*/#include <stdio.h>#include <stdlib.h>#include <string.h>#define OK 1#define ERROR 0#define MAXSIZE 50typedef struct{int value;}RedType; typedef struct{RedType red[MAXSIZE+1];int length;}SqList;SqList *CreateSqList(){int i = 0;int j = 0;char buf[4*MAXSIZE] = "";char *ptr = NULL;SqList *sqlist = (SqList *)malloc(sizeof(SqList));memset(sqlist, 0, sizeof(SqList));printf("请输入待排序数据，以逗号分隔，以分号结束\n""例：23,12,65,36,35;\n""input:");scanf("%s", buf);ptr = buf;sqlist->red[i].value = 0;//red[0]不存值用作哨兵单元i = 1;while(*ptr != ';'){sqlist->red[i].value = atoi(ptr);i++;ptr = strstr(ptr, ",");if(!ptr){break;}ptr++;}sqlist->length = (i - 1);return sqlist;}//将有序的src[start...mid]和src[mid+1...end]归并为有序的TR[start...end]int Merging(RedType src[MAXSIZE+1], RedType *des, int start, int mid, int end){int i = 0;//作为src[start...mid]的游标int j = 0;//作为src[mid+1...end]的游标int k = 0;//作为des[start...end]的游标i = start;j = mid + 1;k = start;for( ; (i <= mid && j <= end); k++)//将src中记录由小到大地并入des{if(src[i].value <= src[j].value){des[k] = src[i];i++;}else{des[k] = src[j];j++;}}if(i <= mid){for( ; i <= mid; i++, k++){des[k] = src[i];}}if(j <= end){for( ; j <= end; j++, k++){des[k] = src[j];}}return OK;}//将src[start...end]归并排序为des[start...end]int MSort(RedType src[], RedType des[], int start, int end){int mid = 0;RedType tmp[MAXSIZE+1];if(start == end){des[start] = src[start];}else{mid = (start + end) / 2;//将src[start..end]平分为SR[start...mid]和SR[mid+1..end]MSort(src, tmp, start, mid);MSort(src, tmp, (mid + 1), end);Merging(tmp, des, start, mid, end);}return OK;}//对顺序表sqlist作归并排序,采用递归的方法int MergingSort(SqList *sqlist){MSort(sqlist->red, sqlist->red, 1, sqlist->length);return OK;}//将src[]中相邻长度为s的子序列两两归并到des[]void MergePass(RedType src[], RedType des[], int s, int length){int i = 1;int j = 0;while(i <= length - 2 * s + 1) { Merging(src, des, i, i + s - 1, i + 2 * s - 1);//两两归并i = i + 2 * s;}if(i < length - s + 1)//归并最后两个序列{Merging(src, des, i, i + s - 1, length);}else//若最后只剩下单个子序列{for(j = i; j <= length; j++)des[j] = src[j];}}//对顺序表sqlist作归并非递归排序void MergingSort2(SqList *sqlist){int k = 1;int* tmp = (RedType *)malloc(sqlist->length * sizeof(RedType));//申请额外空间while(k < sqlist->length){MergePass(sqlist->red, tmp, k, sqlist->length);k = 2 * k;//子序列长度加倍MergePass(tmp, sqlist->red, k, sqlist->length);k = 2 * k;//子序列长度加倍}}//打印表中数据int PrintSqList(SqList sqlist){int i = 0;for(i = 1; i <= sqlist.length; i++){printf("%d,", sqlist.red[i].value);}printf("\b;\n");return OK;}int main(){SqList *sqlist = NULL;SqList *testSqList = NULL;sqlist = CreateSqList();testSqList = (SqList *)malloc(sizeof(SqList));printf("\n递归实现归并排序：\n");memcpy(testSqList, sqlist, sizeof(SqList));PrintSqList(*testSqList);MergingSort(testSqList);PrintSqList(*testSqList);printf("\n非递归实现归并排序：\n");memcpy(testSqList, sqlist, sizeof(SqList));PrintSqList(*testSqList);MergingSort2(testSqList);PrintSqList(*testSqList);free(testSqList);free(sqlist);system("pause");return 0;}