第十章排序 名词解释 1.排序 2.内部排序3.外部排序 4.堆 5.堆排序 、填空 1.若待排序的序列中存在多个记录具有相同的键值,经过排序,这些记录的相对次序仍然保 持不变,则称这种排序方法是的,否则称为 的 2.按照排序过程涉及的存储设备的不同,排序可分为 排序和 排序。 3.按排序过程中依据的不同原则对内部排序方法进行分类,主要有: 等四类。 4在排序算法中,分析算法的时间复杂性时,通常以 和 为标准操作。评价 排序的另一个主要标准是执行算法所需要的 5.常用的插入排序方法有 插入排序、 插入排序 插入排序和 插入排序。 6.以下为直接插入排序的算法。请分析算法,并在 上填充适当的语句 void straightsort(list r) ifor (i= i<=n;i+) r[0]=r[i];j=i-1; while(r[o]. key<r[i]. key)ir[j+1]= r[j+1 7.直接插入排序是稳定的,它的时间复杂性为 空间复杂度为 8.以下为冒泡排序的算法。请分析算法,并在 上填充适当的语句。 void bulbblesort(intn, list r)/*flag为特征位,定义为布尔型* Ifor(i 1++ for(j=1: j<= if(r[j+1]. key <r[j]. key)fflag=0; p=rlj]: r[j]=r[j+1]: r[j+1=p: 1 if(flag) return 9.对于n个记录的集合进行冒泡排序,其最坏情况下所需的时间复杂度是」 10.以下对r[h],r[h+1],…r[p]子序列进行一趟忆速排序。请分析算法,并在 填充适当的语句。 h, int p) i=h;j=p;x=r[i];/*置初值,以第一个记录的键值为标准*/ [while((rLj]. key>=x key)&&(i<j)) /*自尾端进行比较* ;i++;/*将r[j.kiy<x.key的记示移至i所指位置* while((r[i]. key<=x key)&&(i<j)) /*自首行端进行比较*/ if(i<j)[ j-;}/*将r[j].kiy<x.key的记示移至j所指位置*/第十章 排序 一、名词解释 1.排序 2.内部排序 3.外部排序 4.堆 5.堆排序 二、填空 1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保 持不变，则称这种排序方法是________的，否则称为________的。 2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。 3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有：________、________、 ________、________等四类。 4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价 排序的另一个主要标准是执行算法所需要的________。 5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和 ________插入排序。 6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。 void straightsort(list r); {for(i=___________;i<=n;i++) {r[0]=r[i];j=i-1; while(r[0].key<r[j].key){r[j+1]=________;j--;} r[j+1]=_______; } } 7.直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。 8.以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。 void bulbblesort(int n,list r) /*flag 为特征位，定义为布尔型*/ {for(i=1;i<=________;i++) {_______________; for(j=1;j<=_________;j++) if(r[j+1].key<r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=p;} if(flag) return; } } 9.对于 n 个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是________。 10.以下对 r[h],r[h+1],……r[p]子序列进行一趟忆速排序。请分析算法，并在________上 填充适当的语句。 int quickpass(list r,int h,int p) {i=h;j=p;x=r[i];/*置初值，以第一个记录的键值为标准*/ while(i<j) {while((r[j].key>=x.key)&&(i<j))________;/*自尾端进行比较*/ if(i<j) {________;i++;/* 将 r[j].kiy<x.key 的记示移至 i 所指位置*/ while((r[i].key<=x.key)&&(i<j))________;/*自首行端进行比较*/ if(i<j){________;j--;}/* 将 r[j].kiy<x.key 的记示移至 j 所指位置*/ }