第三十七课 实验八 排序实验

教学目的： 掌握简单插入排序、快速排序、堆排序的算法并加以应用。

教学重点：

教学难点：

授课内容：

实现下述三种算法，并用以下无序序列加以验证：

49，38，65，97，76，13，27，49

一、简单插入排序

二、快速排序

三、堆排序

以上算法的C源程序。

#define MAXSIZE 20#define LT(a,b) ((a)<(b))typedef int KeyType;typedef int InfoType;typedef struct{ KeyType key; InfoType otherinfo;}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]; 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]; }}void BInsertSort(SqList *L){ int i,j; int 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; else low=m+1; } for(j=i-1;j>=high+1;--j) L->r[j+1]=L->r[j]; L->r[high+1]=L->r[0]; }}/* QuickSort related function */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;}void 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); }}void QuickSort(SqList *L){ QSort(L,1,L->length);} /* End QuickSort related function*//*SelectSort related function */int SelectMinKey(SqList L,int i){ int k; int j; k=i; for(j=i;j<L.length+1;j++) if(L.r[k].key>L.r[j].key) k=j; return k;}void SelectSort(SqList *L){ RedType t; int i,j; for(i=1;i<L->length;++i){ j=SelectMinKey(*L,i); if(i!=j) { t=L->r[i]; L->r[i]=L->r[j]; L->r[j]=t; } }} /*End SelectSort related function */typedef SqList HeapType;void HeapAdjust(HeapType *H,int s,int m){ RedType rc; int j; rc=H->r[s]; for(j=2*s;j<=m;j*=2){ if(j<m&&LT(H->r[j].key,H->r[j+1].key)) ++j; if(!LT(rc.key,H->r[j].key)) break; H->r[s]=H->r[j]; s=j; } H->r[s]=rc;}void HeapSort(HeapType *H){ RedType t; int i; for(i=H->length/2;i>0;--i) HeapAdjust(H,i,H->length); for(i=H->length;i>1;--i){ t=H->r[1]; H->r[1]=H->r[i]; H->r[i]=t; HeapAdjust(H,1,i-1); }}main(){ int a[]={49,38,65,97,76,13,27,49}; int i,k; SqList s; printf("\nThe record to be sort:\n"); for(i=1;i<9;i++) { s.r[i].key=a[i-1]; printf("%d ",a[i-1]); } s.length=i-1; printf("\n\t1,InsertSort\n\t2,BInsertSort\n\t3,QuickSort\n\t4,SelectSort\n"); printf("\t5,HeapSort\n\tPress 1..5 to select a function\n"); scanf("%d",&k); switch(k){ case 1: InsertSort(&s); break; case 2: BInsertSort(&s); break; case 3: QuickSort(&s); break; case 4: SelectSort(&s); break; case 5: HeapSort(&s); break; default:printf("No function which you select.\n"); } printf("\nThe records be sorted:\n"); for(i=1;i<9;i++) printf("%d ",s.r[i].key); printf("\n\n\tPress any key to exit.\n"); getch();}