#include"stdio.h"#define LT(a,b) ((a)<(b))#define LQ(a,b) ((a)>(b))#define maxsize 20typedef int keytype;typedef struct{keytype key;}RedType;typedef struct{RedType r[maxsize+1];int length;}Sqlist;//直接插入排序void insertsort(Sqlist &L){int i,j;for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}//if}//insertsort//折半插入排序void BInsertSort(Sqlist &L){int i,j,low,high,m;for(i=2;i<=L.length;++i){L.r[0]=L.r[i];low=1;high=i-1;while(low<=high){m=(low+high)/2;if(LT(L.r[0].key,L.r[m].key))high=m-1;elselow=m+1;}//whilefor(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];L.r[high+1]=L.r[0];}//for}//BInsertSort//快速排序int Partition(Sqlist &L,int low,int high){int pivotkey;L.r[0]=L.r[low];pivotkey=L.r[low].key;while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];}L.r[low]=L.r[0];return low;}//Partitionvoid QSort(Sqlist &L,int low,int high){int pivotloc;if(low<high){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}//QSortvoid QuickSort(Sqlist &L){QSort(L,1,L.length);}//QuickSort//简单选择排序int SelectMinKey(Sqlist &L,int m){int i,index=m;for(i=m;i<=L.length;++i){if(LT(L.r[i].key,L.r[index].key))index=i;}return index;}void SelectSort(Sqlist &L){int i,j,temp;for(i=1;i<=L.length;++i){j=SelectMinKey(L,i);if(i!=j){temp=L.r[i].key;L.r[i].key=L.r[j].key;L.r[j].key=temp;}//if}//for}//SelectSort//堆排序void HeapAdjust(Sqlist &L,int s,int m){int rc,j;rc=L.r[s].key;for(j=2*s;j<=m;j*=2){if(j<m&&LT(L.r[j].key,L.r[j+1].key)) ++j;if(!LT(rc,L.r[j].key)) break;L.r[s]=L.r[j];s=j;}//forL.r[s].key=rc;}//HeapAdjustvoid HeapSort(Sqlist &L){int i,temp;for(i=L.length/2;i>0;--i)HeapAdjust(L,i,L.length);for(i=L.length;i>1;--i){temp=L.r[1].key;L.r[1].key=L.r[i].key;L.r[i].key=temp;HeapAdjust(L,1,i-1);}//for}//HeapSort//归并排序void Merge (RedType SR[], RedType TR[], int i, int m, int n) { int j,k;for (j=m+1, k=i; i<=m && j<=n; ++k) {if LQ(SR[i].key,SR[j].key) TR[k] = SR[i++];else TR[k] = SR[j++];}if (i<=m)while (k<=n && i<=m) TR[k++]=SR[i++];if (j<=n)while (k<=n &&j <=n) TR[k++]=SR[j++];} // Mergevoid MSort(RedType SR[], RedType TR1[], int s, int t) { int m;RedType TR2[20];if (s==t) TR1[t] = SR[s];else {m=(s+t)/2;MSort(SR,TR2,s,m);MSort(SR,TR2,m+1,t);Merge(TR2,TR1,s,m,t);}} // MSortvoid MergeSort(Sqlist &L) {MSort(L.r, L.r, 1, L.length);} // MergeSort//冒泡排序void BubbleSort(Sqlist &L){int i,j,temp,index;for(i=1;i<L.length;++i){index=i;for(j=i+1;j<=L.length;++j)if(LT(L.r[j].key,L.r[index].key))index=j;temp=L.r[index].key;L.r[index]=L.r[i];L.r[i].key=temp;}//for}//BubbleSortvoid main(){char c;Sqlist L;int n,i;printf("1-直接插入排序：\n");printf("2-折半插入排序：\n");printf("3-简单选择排序：\n");printf("4-堆排序：\n");printf("5-冒泡排序：\n");printf("6-归并排序：\n");printf("7-快速排序：\n");printf("输入所选排序方法的序号(1~7)：");scanf("%c",&c);printf("input n:");scanf("%d",&n);L.length=n;printf("input the datas:\n");for(i=1;i<=L.length;++i)scanf("%d",&L.r[i]);switch(c){case '1':insertsort(L);break;case '2':BInsertSort(L);break;case '3':SelectSort(L);break;case '4':HeapSort(L);break;case '5':BubbleSort(L);break;case '6':MergeSort(L);break;case '7':QuickSort(L);break;default:printf("没有该序号！\n");}printf("排序后的序列：\n");for(i=1;i<=L.length;++i)printf("%d ",L.r[i]);printf("\n");}。