2022年软件设计师考试知识点（六十四）：排序与查找

很多考生在备考2022年软件设计师考试，希赛小编为大家整理了2022年软件设计师考试知识点（六十四）：排序与查找，供考生备考复习。

排序与查找（★★★★★）

【考法分析】

1、本知识点的主要考查形式有：给定情景描述，指出适用的排序方法；指出特定排序方法的时间复杂度、空间复杂度；指出二分查找的比较次数、比较对象、

时间复杂度；指出散列表查找的相关概念描述是否正确。

【要点分析】

1、顺序查找的思想：将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败。

2、二分法查找的基本思想是：（设R[low,…,high]是当前的查找区)

（1）确定该区间的中点位置：mid=L(low+high)/2˩；

（2）将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下。

若R[mid].key＞k，则由表的有序性可知R[mid,…,n].key均大于k，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,…,mid–1]中。因此，新的查找区间是左子表R[low,…,high]，其中high=mid–1。

若R[mid].key<k，则要查找的k必在mid的右子表R[mid+1,…,high]中，即新的查找区间是右子表R[low,…,high]，其中low=mid+1。

若R[mid].key=k，则查找成功，算法结束。

（3）下一次查找是针对新的查找区间进行，重复步骤（1）和（2）。

（4）在查找过程中，low逐步增加，而high逐步减少。如果high<low，则查找失败，算法结束。

折半查找在查找成功时关键字的比较次数最多为 L  log2n +1  ˩   次。

折半查找的时间复杂度为 O(log2n)次。

【例题】请给出在含有12个元素的有序表｛1，4，10，16，17，18，23，29，33，40，50，51｝中二分查找关键字17的过程。

比较次数：4次；比较对象a[6]，a[3]，a[4]，a[5]。

3、散列表查找的基本思想是：已知关键字集合U，最大关键字为m，设计一个函数Hash，它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间T[0..n-1](n<<m)中，这个区间就称为散列表，散列查找中使用的转换函数称为散列函数。

开放定址法是指当构造散列表发生冲突时，使用某种探测手段，产生一个探测的散列地址序列，并且逐个查找此地址中是否存储了数据元素，如果没有，则称该散列地址开放，并将关键字存入，否则冲突，继续查找下一个地址。

例：记录关键码为（3，8，12，17，9），取m=10（存储空间为10），p=5，散列函数h=key%p。

4、排序分类

5、直接插入排序：即当插入第i个记录时，R1，R2，…，Ri-1均已排好序，因此，将第i个记录Ri依次与Ri-1，…，R2，R1进行比较，找到合适的位置插入。它简单明了，但速度很慢。

注：对于基本有序的序列，选择直接插入排序方法，时间复杂度近乎线性为：O(n)。

6、希尔（Shell）排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt–l<O<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

7、直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换……依次类推，直到所有记录排完为止。

8、堆排序

（1）堆的定义：设有n个元素的序列{K1，K2，…，Kn}，当且仅当满足下述关系之一时，称之为堆。

(i) Ki≤K2 i 且Ki≤K2 i +1；

(ii) Ki≥K2 i 且Ki≥K2 i +1 。

其中(i)称为小顶堆，(ii)称为大顶堆。

（2）堆排序的基本思想为：先将序列建立堆，然后输出堆顶元素，再将剩下的序列建立堆，然后再输出堆顶元素，依此类推，直到所有元素均输出为止，此时元素输出的序列就是一个有序序列。

（3）堆排序的算法步骤如下(以大顶堆为例)：

(i)初始时将顺序表R[1..n]中元素建立为一个大顶堆，堆顶位于R[1]，待序区为R[1..n]。

(ii)循环执行步骤3～步骤4，共n-1次。

(iii)假设为第i 运行，则待序区为R[1..n-i+1]，将堆顶元素R[1]与待序区尾元素R[n-i+1]交换，此时顶点元素被输出，新的待序区为R[1..n-i ]。

(iv)待序区对应的堆已经被破坏，将之重新调整为大顶堆。

（4）堆排序时间复杂度为：O(nlog2n)，是不稳定的排序。

9、冒泡排序的基本思想是，通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移向顶部。由于整个排序的过程就像水底下的气泡一样逐渐向上冒，因此称为冒泡算法。

10、快速排序采用的是分治法，其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题。通过递归地解决这些子问题，然后再将这些子问题的解组合成原问题的解。

快速排序通常包括两个步骤：

第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录都分成两组，第1组都小于该数，第2组都大于该数，如图所示。

第二步，采用相同的方法对左、右两组分别进行排序，直到所有记录都排到相应的位置为止。

11、归并也称为合并，是将两个或两个以上的有序子表合并成一个新的有序表。若将两个有序表合并成一个有序表，则称为二路合并。合并的过程是：比较A[i]和A[j]的排序码大小，若A[i]的排序码小于等于A[j]的排序码，则将第一个有序表中的元素A[i]复制到R[k]中，并令i和k分别加1；如此循环下去，直到其中一个有序表比较和复制完，然后再将另一个有序表的剩余元素复制到R中。

12、基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。基数排序不是基于关键字比较的排序方法，它适合于元素很多而关键字较少的序列。基数的选择和关键字的分解是根据关键字的类型来决定的，例如关键字是十进制数，则按个位、十位来分解。

【备考点拨】

1、掌握顺序查找的相关概念；

2、掌握二分查找的过程；

3、掌握散列表的位置分布和冲突相关的概念；

4、掌握常见排序方法的分类、时间复杂度、空间复杂度、稳定性等；

5、掌握常见排序方法的排序过程（堆排序了解其排序过程）。