第十章 排序参考答案
二、填空
1．稳定、不稳定 2.内部、外部
3．插入排序、交换排序、选择排序、归并排序 4.键值比较、记录移动、附加空间
5．直接、折半、表、希尔 6.2、r[j]、r[0] 7.O（n2）、O（1） 8.n-1、flag=1、n-i
9.O(n) 10.j--、r[i]=r[j]、j++、r[j]=r[i]、x
2
11.O(nlog2n)、O(n) 12.n-1、k=j、k!=I 13.O(n2) 14.n-1、存储区
15.叶子、树根、＋∝ 16.n-1、log2n、O(nlog2n) 17.完全二叉树、n/2 18.O(1)、O(nlog2n) 19.a[ii]、ii++、a[j]、j++、m、n、O(n-h+1) 20.有序 21．O(log2n) 22.O(n2)
23.冒泡排序、快速排序 24.插入排序、快速排序 三、单项选择
1. ③ 2. ③ 3. ② 4. ② 5. ② 6. ② 7. ③ 8. ④ 9. ① 10. ③ 11. ② 12. ③ 13. ③ 14. ④ 15. ④ 16. ③ 17. ③ 18. ② 19. ④ 20. ④ 21. ④ 22. ② 23. ③ 四、简答及应用
1．①直接插入排序
序号 1 2 3 4 5 6 7 8 9 10 11 12 关键字 83 40 63 13 84 35 96 57 39 79 61 15
i = 2 40 83 [63 13 84 35 96 57 39 79 61 15] i = 3 40 63 83 [13 84 35 96 57 39 79 61 15] i = 4 13 40 63 83 [84 35 96 57 39 79 61 15] i = 5 13 40 63 83 84 [35 96 57 39 79 61 15] i = 6 13 35 40 63 83 84 [96 57 39 79 61 15] i = 7 13 35 40 63 83 84 96 [57 39 79 61 15] i = 8 13 35 40 57 63 83 84 96 [39 79 61 15] i = 9 13 35 39 40 57 63 83 84 96 [79 61 15] i = 10 13 35 39 40 57 63 79 83 84 96 [61 15] i = 11 13 35 39 40 57 61 63 79 83 84 96 [15] i = 12 13 15 35 39 40 57 61 63 79 83 84 96 ②直接选择排序
序号 1 2 3 4 5 6 7 8 9 10 11 12 关键字 83 40 63 13 84 35 96 57 39 79 61 15
i = 1 13 [40 63 83 84 35 96 57 39 79 61 15]
i = 2 13 15 [63 83 84 35 96 57 39 79 61 40] i = 3 13 15 35 [83 84 63 96 57 39 79 61 40] i = 4 13 15 35 39 [84 63 96 57 83 79 61 40] i = 5 13 15 35 39 40 [63 96 57 83 79 61 84] i = 6 13 15 35 39 40 57 [96 63 83 79 61 84]
1
2
i = 7 13 15 35 39 40 57 61 [63 83 79 96 84] i = 8 13 15 35 39 40 57 61 63 [83 79 96 84] i = 9 13 15 35 39 40 57 61 63 79 [83 96 84] i = 10 13 15 35 39 40 57 61 63 79 83 [96 84] i = 11 13 15 35 39 40 57 61 63 79 83 84 [96] ③快速排序
关键字 83 40 63 13 84 35 96 57 39 79 61 15 第一趟排序后 [15 40 63 13 61 35 79 57 39] 83 [96 84] 第二趟排序后 [13] 15 [63 40 61 35 79 57 39] 83 84 [96] 第三趟排序后 13 15 [39 40 61 35 57] 63 [79] 83 84 96 第四趟排序后 13 15 [35] 39 [61 40 57] 63 79 83 84 96 第五趟排序后 13 15 35 39 [57 40] 61 63 79 83 84 96 第六趟排序后 13 15 35 39 40 [57] 61 63 79 83 84 96 第七趟排序后 13 15 35 39 40 57 61 63 79 83 84 96
④堆排序
关键字： 83 40 63 13 84 35 96 57 39 79 61 15
排序成功的序列：96 84 83 79 63 61 57 40 39 35 15 13 排序过程如图简答题8－1.1、8－1.2、8－1.3所示。
⑤归并排序
关键字 83 40 63 13 84 35 96 57 39 79 61 15 第一趟排序后 [40 83] [13 63] [35 84] [57 96] [39 79] [15 61] 第二趟排序后 [13 40 63 83] [35 57 84 96] [15 39 61 79] 第三趟排序后 [13 35 40 57 63 83 84 96] [15 39 61 79] 第四趟排序后 13 15 35 39 40 57 61 63 79 83 84 96
2．稳定排序有直接插入、冒泡排序、归并排序。
不稳定排序有快速排序、直接选择排序、堆排序。举例如下： ①快速排序
初始状态 40 65 38 49 97 65 13 60 排序后 13 38 40 49 60 65 65 97 （65表示记录初始位置在65记录位置之后） ②堆排序
初始状态 65 38 75 97 80 13 27 65 排序后 13 27 38 65 65 75 80 97 ③直接排序
初始状态 40 65 38 49 97 65 13 60 排序后 13 38 40 49 60 65 65 97
3．直接选择相对于树形选择排序的优点：算法易懂，容易实现，基本上不需要附加
空间。而树形排序需要附加n – 1附加空间。
直接选择排序相对于树形选择排序的缺点：直接选择排序每一趟都不保留比较结果比较次数较多，而树形排序则能利用大部分上一次的比较结果，因此时间性能比直接选择排序
优越。
堆排序相对于树形排序的优点：堆排序除建第一个堆费时外，其余元素进行堆比较次
2
数小于等于h（h表示n元素构成的完全二叉树的深度），而树形排序每次比较都是h次。因此，堆排序时间复杂度小于树形排序。堆排序基本也不需要附加空间。
4．直接插入排序、直接选择排序、快速排序、堆排序和归并排序时空性如表：
直接插入 直接选择 快速排序 堆排序 归并排序
从上表可以得出：就平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下，时间性能不如堆排序和归并排序。 而后两者相比的结果是，当n较大时，归并排序所需时间优于堆排序，但它所需辅助空间最多。
注意，在所有排序方法中，没有哪一种是绝对最优的，有的适用于n较大的情况，有适用于n较小的情况，还有的与关键字的分布和初始位置有关„„因此，在实际使用时，需要根据不同情况适当选用排序方法，甚至可将多种方法结合使用。
5．分析：先按序列画出对应的完全二叉树，再看其是否满足堆的定义。按这一思路，画出的完全二叉树见图简答8-5.1.
显然序列⑴是堆，而序列⑵不是堆，值为7的元素应该上调，调整过程见图简答题8-5.2. 6.第一趟： [46, 58, 15, 45, 90, 18, 10, 62] [46, 58, 15, 45, 90, 18, 10, 62] . 一次交换之后 [10, 58, 15, 45, 90, 18, 46, 62] 二次交换之后 [10, 46, 15, 45, 90, 18, 58, 62] 三次交换之后 [10, 18, 15, 45, 90, 46, 58, 62] [10, 18, 15, 45, 90, 46, 58, 62]
[10, 18, 15, 45, 90, 46, 58, 62] 四次交换之后 [10, 18, 15, 45, 46, 90, 58, 62]
以上“－”表示当前经比较不交换位置的元素。“ ”表示当前经比较交换位置的元素。 第一趟： [10 18 15 45] 46 [90 58 62] 第二趟： 10 [18 15 45] 46 [62 58] 90 第三趟： 10 [15] 18 45] 46 [58] 62 90 结果： 10 15 18 45 46 58 62 90 7．
⑴插入排序的每趟的结果
初始值健值序列 [12] 5 9 20 6 31 24 i=2 [5 12] 9 20 6 31 24 i=3 [5 9 12] 20 6 31 24
3
平均时间 O(n2) O(n2) O(nlg2n) O(nlog2n) O(nlog2n) 最坏情况 O(n2) O(n2) O(n2) O(nlog2) O(nlog2n) 辅助空间 O(n1) O(1) O(nlog2n) O(1) O(n) i=4 i=5 i=6 i=7 [5 [5 [5 [5 9 6 6 6 12 20] 6 31 24 9 12 20] 31 24 9 12 20 31] 24 9 12 20 24 31]
⑵冒泡排序的每趟的结果：
初始键值序列 [12 5 9 20 6 31 24] 第一趟之后 [5 9 12 6 20 24] 31 第二趟之后 [5 9 6 12 20] 24 31 第三趟之后 [5 6 9 12] 20 24 31 第四趟之后 5 6 9 12 20 24 31
五、算法设计
1.分析：每趟从单链表头部开始，顺序查找当前链值最小的结点。找到后，插入到当前的有序表区的最后。
Void selesort ( lklist L ) /* 设链表L带头结点 */ { q=L; /* 指向第一数据前趋 */ while ( q-> next !=NULL )
{ pl = q -> next ;
minp =pl; /* minp指向当前已知的最小数 */ while ( pl -> next != NULL )
{ if ( pl -> next -> data < minp -> data ) minp = pl -> next ; /* 找到了更小数 */ pl = pl -> next ; /* 继续往下找 */
}
if ( minp != q -> next) /* 将最小数交换到第一个位置上 */
{ r1 = minp -> next ;
minp -> next = r1 -> next ; /* 删除最小数 */ r2 = q -> next ;
q -> next = r2 -> next ; /* 删除当前表中第一个数 */ r1 -> next = q -> next ;
q -> next = r1 ; /* 将最小数插入到第一个位置上 */ r2 -> next = minp -> next ;
minp -> next = r2 ; /* 将原第一个数放到最小数原位置上 */ }
q = q > next ; /* 选择下一个最小数 */
}
}
2.分析：先调用划分函数 quickpass () ,以确定中间元素的位置，然后再借助栈分别对
中间元素左、右两边的区域进行快速排序。
Void qksort ( list A ) /* n为元素个数 */
{ InitStack ( S ) ; /* 设置一个栈保存有关参数和变量 */ j = 1 ; h = n ; /* j , h 分别指向表头和表尾 */ while ( ( j < h ) ‖( !empty ( S ) ) )
{ while ( j < h )
{ quickpass ( A,j,h,i ) ; /* 划分函数 quickpass () 参照教材 */ push ( S,j,h,i ) ; /* 保存变量值 */
h = i – 1 ; /* 设置对左边进行划分的参数 */
4
}
if ( !empty ( S ) )
{ pop ( S,j,h,i ) ; /* 取出变量值 */
j = i + 1 ; /* 设置对右边进行划分的参数 */ } }
}
3．分析：插入排序的基本思想是：每趟从无序区间中取出一个元素，再按键值大小插入到前面的有序区间中。对于有序区，当然可以用二分查找来确定插入位置。
Void straightsort ( list A ) /* n为元素个数，数组下标从1开始，到n结束。 */ { for ( i =2 ; i <= n ; i + + )
{ low = 1 ; high = i – 1 ; /* low ,high 分为当前元素上、下界 */
A[0] . key = A[i] . key ; While ( low <= high )
{ mid = ( low + high ) /2 ; switch
{ case : A[0] . key <= A[mid] . key : high = mid – 1 ; /* 修改上界 */ case : A[0] . key > A[mid] . key : low = mid + 1 ; /* 修改下界 */ }
for ( j = i-1 ; j >= mid ; j - -) A [j +1] = A [ j ] ; /* 移动数据 */
A[ mid ] = A[ i ] ; }
} }
4．分析：本题的算法思想是：先设置好上、下界，然后分别从线性表两端查找正数和负数，找到后进行交换，直到上、下界相遇。
Void example ( datatype A [n] )
{ i = 1, j = n ; /* i , j为左右边界 */ while ( i < j )
{ while ( ( i < j ) && ( A[ i ] < 0 ) ) i++ ; /* 在左边界找正数 */ while ( (i < j ) && ( A[ j ] > 0 )) j - - ; /* 在右边界找负数 */ if ( i < j)
{ temp = A[ i ]; A[ i ] = A[ j ]; A[ j ] = A [temp ] ; /*交换两个元素的值 */ i++ ; j - -; } }
}
5．分析：此问题分为两个算法，第一个算法 shift 假设 a[ 1] , a[ 2 ],„,a[ k]为堆，增加一个无素a[ k + 1 ],把数组a[ 1 ],a[ 2 ], „,a[ k + 1 ]调整为堆。第二个算法heep 从1开始调用算法sift将整个数组调整为堆。
Void sift (datatype A[ n ] , int K) /* n > = k + 1 */
{ x = A[ K+1] ; i = K +1 ;
while ( ( i/2 > 0 )&&( A[i/2]>x) ) { A[i]= A[i./2]; i = i/2;} /*从下往上插入位置 */
5
A[i] = x ;
}
Void heap ( datatype A[ n ] ) ; /* 从1开始调用算法sift ，将整个数组调整为堆 */
{ for ( k = 1 ; k <= n-1; k++ ) sift ( A,k ) ; }
6．分析：本算法采用的存储结构是带头结点的双循环链表。首先找元素插入位置，然后把元素从原链表中删除，插入到相应的位置处。请注意双链表上插入和删除操作的步骤。
Void sort ( dlklist H ) /* 链表H采用带头结点的双循环链表 */
{ pre = H -> next ; while ( p != H )
{p = pre -> next ; /* p是有序表的末尾 */ q = p -> next ; /* 保存下一个插入元素 */
while((pre!=H)&&(p->data
data))pre=pre–prior; /*从后往前找插入位置 */if ( pre ! =p -> prior )
{ p-> prior->next = p -> next ; /* 删除p */
p-> next->prior = p -> prior;
p->next = pre ->next ; /* 插入到pre之后 */ pre -> next -> prior = p ;
p ->prior= pre ; pre ->next = p ; } p=q; }
}
6
因篇幅问题不能全部显示，请点此查看更多更全内容