牛客专题练习02

解析:
分块查找:即又称索引顺序查找,这是顺序查找的一种改进的方法.在此查找法中,除表本身以外,尚需建立一个"索引表",其包含两项内容:关键字项(其值为该字表中最大的关键字)和指针项(指示该字表的第一个记录在表中的位置).所谓分块指的是第二个子表中所有的关键字都比第一个表中的关键字大,同理,第三个字表都大于第二个字表中的所有的关键字..
通常,分块查找的过程需要分两步:先确定待查记录所在的块(字表),然后在块中顺序查找.

举个例子：比如要找14309号房间，先找到14号楼，再到第三楼，最后再找09号房间

解析：

第一趟：1 2 3 4

第二趟：3 4

第三趟：3

解析：在待排数据基本有序的情况下,直接插入排序方法是效果最好。所以选A

解析：二分查找:n,n/2，n/4…令n/2*k=1. 得k=log2n（以2为为底的对数）

解析：正确，堆的空间复杂度为1，快速排序为log2（n），归并为n

题中有错误：B选项应该是9 18 15 19 23 23

解析:

第一趟：18 19 9 23 15 23

第二趟：18 9 19 15 23 23

第三趟：9 18 15 19 23 23

解析：例如:        A[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18]

第一趟：A[9] 0 1 2 3 4 5 6 7 8

第二趟：A[4] 0 1 2 3 4

第三趟：A[2] 3 4

第四趟：A[3] 3

解析:

A、B、C三个选项的序列都不是有序的，快速排序的时间复杂度为O(nlogn)。

D选项的序列已经是有序的了，因此它快速排序的复杂度为O(n^2)。

故答案为：D

解析：

选择排序的思想是：第i趟排序，找到L[i...n]中最小的元素与L(i)交换位置，这样保证每一趟排序确定一个元素的最终位置。

第一趟：1,15,12,18,2,35,30,11
第二趟：1,2,12,18,15,35,30,11
第三趟：1,2,11,18,15,35,30,12
第四趟：1,2,11,12,15,35,30,18
第五趟：1,2,11,12,15,18,35,30
第六趟：1,2,11,12,15,18,30,35

解析:

基数排序：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次

排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。可以同时操作多个元素，从而实现了并行处理。