high = mid-1; // 在左子表上继续查找 else
low = mid+1; // 在右子表上继续查找 }
return -1; // 查找失败,返回-1 }
第九章 排序
一、填空题 1、插入、堆 2、快速、归并 3、O(n2)、O(n) 4、?n/2?-1、n-1 5、O(log2n)、O(nlog2n) 6、84 79 56 30 40 46 7、O(nlog2n)、O(n2) 8、O(log2n)、O(n) 9、两端、中间
10、38 40 46 56 79 80 11、4 4
12、 ?log2n? 或 ?log2n?+1 13、O(n)、O(n log2n)、O(n) 14、6、4、8
15、 38 46 56 79 40 80 二、应用题
(1) ( 46 ) ( 74 16 53 14 26 40 38 86 65 27 34 ) ← 初态 ( 46 74 ) ( 16 53 14 26 40 38 86 65 27 34 ) ( 16 46 74 ) ( 53 14 26 40 38 86 65 27 34 ) ( 16 46 53 74 ) ( 14 26 40 38 86 65 27 34 ) ( 14 16 46 53 74 ) ( 26 40 38 86 65 27 34 ) ( 14 16 26 46 53 74 ) ( 40 38 86 65 27 34 ) ( 14 16 26 40 46 53 74 ) ( 38 86 65 27 34 ) ( 14 16 26 38 40 46 53 74 ) ( 86 65 27 34 ) ( 14 16 26 38 40 46 53 74 86 ) ( 65 27 34 ) ( 14 16 26 38 40 46 53 65 74 86 ) ( 27 34 ) ( 14 16 26 27 38 40 46 53 65 74 86 ) ( 34 ) ( 14 16 26 27 34 38 40 46 53 65 74 86 )
(2) ( 46 74 16 53 14 26 40 38 86 65 27 34 ) ← 初态 ( 14 )( 74 16 53 46 26 40 38 86 65 27 34 ) ( 14 16 )( 74 53 46 26 40 38 86 65 27 34 )
( 14 16 26 )( 53 46 74 40 38 86 65 27 34 ) ( 14 16 26 27 )( 46 74 40 38 86 65 53 34 ) ( 14 16 26 27 34 )( 74 40 38 86 65 53 46 ) ( 14 16 26 27 34 38 )( 40 74 86 65 53 46 ) ( 14 16 26 27 34 38 40 )( 74 86 65 53 46 ) ( 14 16 26 27 34 38 40 46 )( 86 65 53 74 ) ( 14 16 26 27 34 38 40 46 53 )( 65 86 74 ) ( 14 16 26 27 34 38 40 46 53 65 )( 86 74 ) ( 14 16 26 27 34 38 40 46 53 65 74 86 )
(3) ( 46 74 16 53 14 26 40 38 86 65 27 34 ) ← 初态 构造初始堆过程:(构造大根堆)
( 46 74 16 53 14 34 40 38 86 65 27 26 ) ( 46 74 16 53 65 34 40 38 86 14 27 26 ) ( 46 74 16 86 65 34 40 38 53 14 27 26 ) ( 46 74 40 86 65 34 16 38 53 14 27 26 ) ( 46 86 40 74 65 34 16 38 53 14 27 26 ) ( 86 74 40 53 65 34 16 38 46 14 27 26 )
初始堆对应的完全二叉树: 堆排序过程:
( 74 65 40 53 27 34 16 38 46 14 26 )( 86 ) ( 65 53 40 46 27 34 16 38 26 14 )( 74 86 ) ( 53 46 40 38 27 34 16 14 26 )( 65 74 86 )