(第9章习题答案.docVIP

习题9 1.在各种排序方法中，哪些是稳定的？哪些是不稳定的？对不稳定的排序方法举出一个不稳定的例子。 解： 排序方法 平均时间 最坏情况 辅助空间 稳定性 不稳定排序举例 直接插入排序 折半插入排序 二路插入排序 表插入排序 起泡排序 直接选择排序 希尔排序 快速排序 堆排序 2-路归并排序 基数排序 稳定 稳定 稳定 稳定 稳定 不稳定 不稳定 不稳定 不稳定 稳定 稳定 2,2,1 3,2,2,1(d=2，d=1) 2,2,1 2,1,1(大顶堆) 2.若不考虑基数排序，则排序的两种基本操作是什么？ 解：关键字的比较和记录的移动。 3.外排序的基本操作是什么？ 解：生成有序归并段，归并。 4.分别采用堆排序、快速排序、起泡排序和归并排序，对初始状态为有序的表，则最省时间的是哪种排序方法？最费时间的是哪种排序方法？ 解：起泡排序，快速排序。 5.不受待排序初始序列的影响的排序算法是哪种？其时间复杂度是多少？ 解：简单选择排序，时间复杂度是。 6.直接插入排序设置监视哨的作用是什么？ 解：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。 7.从平均时间性能而言，哪种排序方法最佳？ 解：快速排序。 8.设待排序的记录有10个，其关键字分别为{75，23，98，44，57，12，29，64，38，82}。手工执行以下排序算法(按字典序比较关键字的大小)，写出每一堂排序结束时的关键字的状态： (1)直接插入排序 (2)折半插入排序 (3)起泡排序 (4)简单选择排序 (5)快速排序 (6)希尔排序 (7)2-路归并排序 (8)基数排序 解：略 9.已知记录序列R[1..n]中的关键字各不相同，可按如下所述实现计数排序：另设数组C[1..n]，对每个记录R[i]，统计序列中关键字比它小的记录个数存于C[i]，则C[i]=0的记录必为关键字最小的记录，然后依C[i]值的大小对R中记录进行重新排列，试编写实现上述排序的算法。 解：void Count_Sort(int R[],int n){//计数排序算法 int C[MAX]; for(i=0;in;i++){//对每一个元素 for(j=i,count=0;jn;j++) //统计关键字比它小的元素个数 if(R[j]R[i])count++; C[i]=count; } for(i=0;in;i++){//依次求出关键字最小,第二小,...,最大的记录 min=i; for(j=i+1;jn;j++) if(C[j]C[min]) min=j; //求出最小记录的下标min temp=R[i];R[i]=R[min]; R[min]=temp; //与第i个记录交换 C[min]=C[i]; } }//Count_Sort 10.已知奇偶交换算法如下描述：第一趟对所有奇数的i，将R[i]和R[i+1]进行比较，第二趟对所有偶数的i，将R[i]和R[i+1]进行比较，每次比较时若R[i]R[i+1]，则将两者交换，以后重复上述二趟过程，直到整个数组有序。 (1)试问排序结束的条件是什么？ (2)编写一个实现上述排序过程的算法。 解：void OE_Sort(int R[ ],int n){//奇偶交换排序的算法 change=1; while(change){ change=0; for(i=1;in-1;i+=2) //对所有奇数进行一趟比较 if(R[i]R[i+1]){ temp=R[i]; R[i]=R[i+1]; R[i+1]=temp; change=1; } for(i=0;in-1;i+=2) //对所有偶数进行一趟比较 if(R[i]R[i+1]){ temp=R[i]; R[i]=R[i+1]; R[i+1]=temp; change=1; } }//while }//OE_Sort 本算法的结束条件是连续两趟比较无交换发生。 11.编写算法，对n个关键字取整数值的记录进行整理，使得所有关键字为负值的记录排在关键字为非负值的记录之前，要求： (1)采用顺序存储结构，至多使用一个记录的辅助存储空间。 (2)算法的时间复杂度为。 (3)讨论算法中记录的最大移动次数。 解：void Divide(int R[],int n){//把数组R中所有值