归并排序

归并排序 /* 归并排序*/ #include "stdio.h" #define ERROR -1 #define OK 1 #define NULL 0 #define MAXSIZE 20 /* 顺序表的最大长度*/ typedef int KeyType; /* 定义关键字类型为整数类型*/ typedef struct { KeyType key; /* 关键字项*/ int od; /* 其他数据项*/ } RedType; /* 记录类型*/ typedef struct { RedType r[MAXSIZE+1]; /* r[0]闲置或作哨兵单元*/ int length; /* 顺序表的当前长度*/ } SqList; /* 顺序表类型*/ void Merge(RedType SR[] , RedType TR[], int i, int m, int n){ /* 已知SR[i..m]和SR[m+1..n]分别按关键字有序，将它们归并为 一个有序序列并存放在TR[i..n]中 */ int j, k; for (j=m+1,k=i; i<=m&&j<=n; ++k) { /* 将SR中记录从小到大并入TR */ if (SR[i].key <= SR[j].key) { TR[k].key=SR[i].key; TR[k].od=SR[i].od; ++i; } else { TR[k].key=SR[j].key; TR[k].od=SR[j].od; ++j; } } while ( i<=m ) { /* 将剩余的SR[i…m]复制到TR */ TR[k].key = SR[i].key; TR[k].od = SR[i].od; ++i; ++k; } while ( j<=n ) { /* 将剩余的SR[j…n]复制到TR */ TR[k].key = SR[j].key; TR[k].od = SR[j].od; ++j; ++k; } } /* Merge */ void MSort(RedType SR[], RedType TR1[], int s, int t){ /* 将SR[s..t]归并排序为TR1[s..t] */ RedType TR2[MAXSIZE+1]; int m; if(s==t) { TR1[s].key = SR[s].key; TR1[s].od = SR[s].od; } else { m = (s+t)/2; /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */ MSort(SR, TR2, s, m); /* 递归地将SR[s..m]归并为有序的TR2[s..m] */ MSort(SR, TR2, m+1, t); /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */ Merge(TR2, TR1, s, m, t); /* 将TR2[s..m]和TR2[m+1..t]归并为TR1[s..t] */ } } /* MSort */ main(){ SqList *L; int i, n=10; printf("\n"); for(i=1; i<=10; ++i) { scanf("%d", &L->r[i].key); L->r[i].od = i; } L->length = n; MSort(L->r, L->r, 1, L->length); for(i=1; i<=10; ++i) printf("\t[%2d] %4d; ", L->r[i].od, L->r[i].key); getch(); }_