数据结构教学作者主编马世霞第8章节排序课件幻灯片.ppt

8.4.2 堆排序 注意，没有一种排序方法的效率是在任何情况下都能独占鳌头的，具体采取哪种方法要根据实际情况而定。 假设在10000个随机的数据中找出最大的10个数，那么采用堆排序应该是最合适的，因为： 第一，经验指出堆排序是一个非常稳定的算法，在各种环境中 其效率变化不会太大； 第二，堆排序的特性决定了只要构建一棵根节点为最大数的优先队列树，然后取其前10个根节点就行了。 【例8-1】编程实现数据的排序。 8.5 二路归并排序 归并排序：多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。 假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，如图所示。 二路归并排序的基本操作是将两个有序表合并为一个有序表。 8.5 二路归并排序 将有序文件a[low..mid]和a[mid+1..high]归并为b[low..high]的算法 void Merge(int a[], int low, int mid, int high) /*实现一趟归并排序*/ { int b[MaxSize],i, j, k; i=low, j=mid+1, k=0; /*置初始值*/ while(i=mid j=high) { if(a[i]=a[j]){b[k]=a[i]; i++; k++;} else {b[k]=a[j]; j++; k++;} } while(i=mid) {b[k]=a[i]; i++; k++;} while(j=high) {b[k]=a[j]; j++; k++;} for(k=0,i=low;i=high;k++,i++) a[i]=b[k]; /*排序完成*/ } void Merge_Sort(int a[],int low,int high) { int mid; if(lowhigh) /*区间长度大于1*/ { mid=(low+high)/2; Merge_Sort (a,low,mid); Merge_Sort (a,mid+1,high); Merge(a,low,mid,high); } } 8.5 二路归并排序 对n个元素的表，将这n个元素看作叶结点，若将两两归并生成的子表看作它们的父结点，则归并过程对应由叶向根生成一棵二叉树的过程。 所以归并趟数约等于二叉树的高度-1，即log2n，每趟归并需移动记录n次，故时间复杂度为O(nlog2n)。 【例8-2】编程，实现二路归并排序。 8.6 基数排序 基数排序：一种借助于多关键码排序的思想，是将单关键码按基数分成“多关键码”进行排序的方法。 1.多关键码排序 2. 链式基数排序 8.6 基数排序 【例8-3】设待排序的表有10个记录，说明采用基数排序方法进行排序的过程。其关键字为｛178，109，063，930，589，184，505，269，008，083｝。 总结 总结分内部排序方法，可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序，如表所示。 8.7 应用举例 【例8-3】学生管理系统中的学生总成绩排序模块设计。 要求：学生信息包括学号、数学成绩、英语成绩和总成绩内容，输入学生信息后，要求按照总成绩从高到低的顺序输出。 实现：利用冒泡排序实现学生成绩排序功能。 知识点：冒泡排序的算法； 8.7 应用举例 #include stdio.h typedef struct { int id;//学号 int math;//数学成绩 int english;//英语成绩 int sumscore;//总成绩 }stu; void Bubble_Sort(stu a[],int n) //冒泡排序函数 { int i,j; stu temp; for(i=0;in-1;i++) for(j=n-1;ji;j--) { if(a[j].sumscorea[j-1].sumscore) 8.7 应用举例 { temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; } } } main() { stu a[5]; int i; printf(请输入学号,数学成绩,英语成绩(用，隔开):\n); for(i=0;i5;i++) { scanf(%ld,%d,%d,a[i].id,a[i].math,a[i].english); a[i].sumscore=a[i].math+a[i].eng