插入、交换、选择、归并.docx

#define MAXSIZE 20#define int KeyType;typedef struct {KeyType key;infoType otherinfo;}RedType;typedef struct {RedType r[MAXSIZE+1];int length;}SqList;}//插入排序void InsertSort(SqList L) { // 对顺序表L作直接插入排序。 int i,j; for (i=2; i=L.length; ++i) if (LT(L.r[i].key, L.r[i-1].key)) { // 时，需将L.r[i]插入有序子表 L.r[0] = L.r[i]; // 复制为哨兵 for (j=i-1; LT(L.r[0].key, L.r[j].key); --j) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置 }} // InsertSort //交换排序void BubbleSort(SeqList R) {　　int i，j;　　Boolean exchange; //交换标志　　for(i=1;in;i++){ exchange=FALSE; j=n-1;j=i;j--) //对当前无序区R[i..n]自下向上扫描　　 if(R[j+1].key R[j].key){//交换记录　　 R[0]=R[j+1]; //R[0]不是哨兵，仅做暂存单元　　 R[j+1]=R[j]; 　　R[j]=R[0];　　 exchange=TRUE; //发生了交换，故将交换标志置为真　　 }　　 if(!exchange) //本趟排序未发生交换，提前终止算法　　 return;　　} //endfor(外循环)} //BubbleSort/n;i++){//选择排序void SelectSort(SqList L) { // 对顺序表L作简单选择排序。 int i,j; for (i=1; i L.length; ++i) { // 选择第i小的记录，并交换到位 j = SelectMinKey(L, i); // 在L.r[i..L.length]中选择key最小的记录 if (i!=j) { // L.r[i]←→L.r[j]; 与第i个记录交换 RedType temp; temp=L.r[i]; L.r[i]=L.r[j]; L.r[j]=temp; } }} // SelectSort//归并排序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 LQ(SR[i].key,SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } if (i =m) // TR[k..n] = SR[i..m]; 将剩余的SR[i..m]复制到TR while (k =n i =m) TR[k++]=SR[i++]; if (j =n) // 将剩余的SR[j..n]复制到TR while (k =n j =n) TR[k++]=SR[j++];} // Merge void MSort(RedType SR[], RedType TR1[], int s, int t) { // 将SR[s..t]归并排序为TR1[s..t]。 int m; RedType TR2[20]; if (s==t) TR1[t] = SR[s]; else { m=(s+t)/2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t] MSort(SR,TR2,s,m); // 递归地