实验四邵彬彬

1《数据结构》实验四排序学号：1008014212姓名：邵彬彬专业：10级计科2班指导教师：郭世懿2实验四排序一、实验目的1．掌握插入排序（直接插入排序、Shell排序）算法的实现方法。2．掌握交换排序（冒泡排序、快速排序）算法的实现方法。3．掌握选择排序（简单的选择排序、堆排序）算法的实现方法。4．掌握二路归并排序算法的实现方法。5．通过排序算法在实际应用中的运用，增强程序设计能力。二、实验要求1．实验前做好充分准备，包括复习所学内容，事先预习好本次实验内容。2．实验时记录实验结果，按要求完成各个设计题目。3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。三、实验题目本次实验给出的选定题目如下表所示。实验名称学时实验内容实验要求实验类型排序2（1）直接插入排序算法、Shell排序算法必做设计性（2）冒泡排序、快速排序算法必做设计性（3）简单选择排序算法、堆排序算法选做设计性（4）班级学生成绩管理（利用某种排序方法实现按某个或某些关键字排序）选做综合性四、实验内容与要求1、实验题目一：直接插入排序算法、SHELL排序算法要求：利用顺序表作为排序表，分别利用直接插入排序及Shell排序方法对其进行排序。2、实验题目二：冒泡排序、快速排序算法要求：利用顺序表作为排序表，分别利用冒泡排序与快速排序方法对其进行排序并加以验证。3、实验题目三：简单选择排序算法、堆排序算法要求：利用顺序表作为排序表，分别利用简单选择排序与堆排序方法对其进行排序并加以验证。4、实验题目四：班级学生成绩管理要求：设计一个班级学生绩管理系统，能够存储全班同学的学号、姓名、各科考试成绩等信息，并能够实现相关查询（按姓名和学号）和排序（按总成绩）操作。五、实验内容：本程序包含了9个函数，它们分别是：（1）、直接插入排序的算法函数InsertSort（）。（2）、希尔排序的算法函数ShellSort（）。（3）、冒泡排序算法函数BubbleSort（）。（4）、快速排序的算法函数Partition（）。3（5）、选择排序算法函数SelectSort（）。（6）、堆排序算法函数HeapAdjust（）。（7）、对存储数字的遍历函数Visit（）。（8）、初始化函数InitSqList（）。（9）、主函数main（）。具体设计：一、直接插入排序voidInsertSort(SqList&L){inti,j;for(i=2;i=L.length;i++){if(L.r[i].keyL.r[i-1].key){L.r[0]=L.r[i];L.r[i]=L.r[i-1];for(j=i-2;(L.r[0].keyL.r[j].key);j--)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}}二、希尔排序voidShellSort(SqList&L){inti,j;intdk=1;//增量while(dk=L.length/3)dk=3*dk+1;//增大增量while(dk0)4{dk/=3;//减小增量for(i=dk;i=L.length;i++){L.r[0].key=L.r[i].key;j=i;while((j=dk)&&(L.r[j-dk].keyL.r[0].key)){L.r[j].key=L.r[j-dk].key;j-=dk;}L.r[j].key=L.r[0].key;}}}三、冒泡排序voidBubbleSort(SqList&L){inti,j;for(i=0;iL.length-2;i++){intflag=1;for(j=0;jL.length-i-2;j++)if(L.r[j].keyL.r[j+1].key){flag=0;inttemp;temp=L.r[j].key;L.r[j].key=L.r[j+1].key;L.r[j+1].key=temp;5}//若无交换说明已经有序if(flag==1)break;}}四、快速排序intPartition(SqList&L,intlow,inthigh){//分割区域函数L.r[0]=L.r[low];intpivotkey=L.r[low].key;//一般将顺序表第一个元素作为支点while(lowhigh){while(lowhigh&&L.r[high].key=pivotkey)high--;L.r[low]=L.r[high];while(lowhigh&&L.r[low].key=pivotkey)low++;L.r[high]=L.r[low];}L.r[low]=L.r[0];//返回枢轴位置returnlow;}voidQSort(SqList&L,intlow,inthigh){//每张子表的快速排序if(lowhigh){6intpivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}voidQuickSort(SqList&L){QSort(L,1,L.length);}五、简单选择排序voidSelectSort(SqList&L){intmin;intj;for(inti=0;iL.length;i++){//选择第i小的记录，并交换j=i;min=L.r[i].key;for(intk=i;kL.length;k++){//在R[i..n-1]中选择最小的记录if(L.r[k].keymin){min=L.r[k].key;j=k;}}if(i!=j){//与第i个记录交换inttemp=L.r[i].key;L.r[i].key=L.r[j].key;7L.r[j].key=temp;}}}六、堆排序voidHeapAdjust(HeapType&H,ints,intm){//堆调整，将记录调整为小顶堆intj;RedTyperc=H.r[s];//暂时存储根结点for(j=2*s;j=m;j*=2){//沿着结点记录较小的向下筛选if(jm&&H.r[j].keyH.r[j+1].key)++j;if(rc.key=H.r[j].key)break;H.r[s]=H.r[j];s=j;}H.r[s]=rc;}voidHeapSort(HeapType&H){inti;RedTypetemp;for(i=H.length;i0;--i)HeapAdjust(H,i,H.length);for(i=H.length;i1;--i){8temp=H.r[1];H.r[1]=H.r[i];H.r[i]=temp;HeapAdjust(H,1,i-1);}}（2）遍历函数与初始化voidVisit(SqListL){for(inti=1;i=L.length;i++)coutL.r[i].key;coutendl;}voidInitSqList(SqList&L,inta[]){for(inti=1;i=L.length;i++)L.r[i].key=a[i];}测试结果：以下是各种界面的测试结果：9