《数据结构》课件第9章.ppt

观察结果会发现，冒泡排序、快速排序的比较和移动次数总是不变，且冒泡排序的效率最高，比较次数仅为99，移动次数为0。如果将冒泡函数BubbleSort()中的“flag?=?0;”一句删除，即无论是否发生交换都不中止排序，则发现冒泡比较4950次，移动0次。这是因为伪随机函数rand()所产生的是一个有序序列，冒泡排序过程中不会发生交换。此时快速排序退化为冒泡排序，所以比较4950次。且由于每趟快速排序时都要经过保存和写回基准记录r[i]的步骤，所以移动次数为2*99?=?198。实训9-2排序算法的应用【实训目的】运用各种排序算法解决实际问题。【实训内容】为奥运会男子110米栏比赛设计排序和查询系统，可分别按选手编号和成绩排序，并提供按编号查询、按编号和名次输出的功能。【实训要求】1.编写完整程序，主函数显示如下菜单：1—输入2—按选手编号排序3—按成绩排序4—按选手编号查询5—按编号输出6—按名次输出0—退出2.编写输入、按选手编号排序(直接选择排序)、按成绩排序(堆排序)、按选手编号查询(折半查找)和输出5个函数。【算法分析】记录至少包括选手编号、成绩等数据项，以数组形式存储。分别以编号和成绩为关键字排序，并将排序结果分别用另外的数组保存。按选手编号进行折半查找要在排序后的结果中进行。【程序清单】#includestdio.h#defineMAXSIZE100typedefstruct{intnumber;floatscore;}RecordType;voidinput(RecordTyper[],intn){inti;for(i=1;i=n;i++){printf(r[%d]的编号成绩:\n,i);scanf(%d%f,r[i].number,r[i].score);}}voidSelectSort(RecordTyper[],intn)/*用直接选择排序方法对r[1],…,r[n]按选手编号进行排序*/{inti,j,k;for(i=1;in;i++) { k=i; for(j=i+1;j=n;j++) if(r[j].numberr[k].number) k=j; if(k!=i) {r[0]=r[i]; /*r[0]用作临时变量，交换r[i]和r[k]*/r[i]=r[k];r[k]=r[0];}}}voidsift(RecordTyper[],intk,intm)/*假设ｒ[k,…,m]是以ｒ[k]为根的完全二叉树，且分别以r[2k]和r[2k+1]为根的左、右子树都是大根堆，通过筛选，使整个序列r[k,…,m]满足堆的性质*/{inti,j;RecordTypex;i=k;j=2*i; /*r[j]是r[i]的左孩子*/x=r[i]; /*移出根结点*/while(j=m){ if(jmr[j].scorer[j+1].score) j++; /*若右孩子较大，则把j修改为右孩子的下标*/ if(x.scorer[j].score) /*若父结点小于孩子结点*/ { r[i]=r[j]; /*将r[j]上移到父结点的位置上*/ i=j; /*以上移子结点的原位置为新的父结点位置，继续向下筛*/ j=2*i; } elsej=m+1; /*父结点不小于子结点，筛选运算完成，令j=m+1，以便中止循环*/}r[i]=x; /*被筛结点的值放入最终位置*/}voidHeapSort(RecordTyper[],intn)/*用堆排序方法对r[1],…,r[n]按成绩进行排序*/{inti;RecordTypew;for(i=n/2;i=1;i--)