很多考生在備考2022年軟件設計師考試，希賽小編為大家整理了2022年軟件設計師考試知識點（六十四）：排序與查找，供考生備考復習。

排序與查找（★★★★★）

【考法分析】

1、本知識點的主要考查形式有：給定情景描述，指出適用的排序方法；指出特定排序方法的時間復雜度、空間復雜度；指出二分查找的比較次數(shù)、比較對象、

時間復雜度；指出散列表查找的相關概念描述是否正確。

【要點分析】

1、順序查找的思想：將待查找的關鍵字為key的元素從頭到尾與表中元素進行比較，如果中間存在關鍵字為key的元素，則返回成功；否則，則查找失敗。

2、二分法查找的基本思想是：（設R[low,…,high]是當前的查找區(qū))

（1）確定該區(qū)間的中點位置：mid=L(low+high)/2?；

（2）將待查的k值與R[mid].key比較，若相等，則查找成功并返回此位置，否則需確定新的查找區(qū)間，繼續(xù)二分查找，具體方法如下。

若R[mid].key＞k，則由表的有序性可知R[mid,…,n].key均大于k，因此若表中存在關鍵字等于k的結點，則該結點必定是在位置mid左邊的子表R[low,…,mid–1]中。因此，新的查找區(qū)間是左子表R[low,…,high]，其中high=mid–1。

若R[mid].key<k，則要查找的k必在mid的右子表R[mid+1,…,high]中，即新的查找區(qū)間是右子表R[low,…,high]，其中l(wèi)ow=mid+1。

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

（3）下一次查找是針對新的查找區(qū)間進行，重復步驟（1）和（2）。

（4）在查找過程中，low逐步增加，而high逐步減少。如果high<low，則查找失敗，算法結束。

折半查找在查找成功時關鍵字的比較次數(shù)最多為 L  log2n +1  ?   次。

折半查找的時間復雜度為 O(log2n)次。

【例題】請給出在含有12個元素的有序表｛1，4，10，16，17，18，23，29，33，40，50，51｝中二分查找關鍵字17的過程。

比較次數(shù)：4次；比較對象a[6]，a[3]，a[4]，a[5]。

3、散列表查找的基本思想是：已知關鍵字集合U，最大關鍵字為m，設計一個函數(shù)Hash，它以關鍵字為自變量，關鍵字的存儲地址為因變量，將關鍵字映射到一個有限的、地址連續(xù)的區(qū)間T[0..n-1](n<<m)中，這個區(qū)間就稱為散列表，散列查找中使用的轉換函數(shù)稱為散列函數(shù)。

開放定址法是指當構造散列表發(fā)生沖突時，使用某種探測手段，產(chǎn)生一個探測的散列地址序列，并且逐個查找此地址中是否存儲了數(shù)據(jù)元素，如果沒有，則稱該散列地址開放，并將關鍵字存入，否則沖突，繼續(xù)查找下一個地址。

例：記錄關鍵碼為（3，8，12，17，9），取m=10（存儲空間為10），p=5，散列函數(shù)h=key%p。

4、排序分類

5、直接插入排序：即當插入第i個記錄時，R1，R2，…，Ri-1均已排好序，因此，將第i個記錄Ri依次與Ri-1，…，R2，R1進行比較，找到合適的位置插入。它簡單明了，但速度很慢。

注：對于基本有序的序列，選擇直接插入排序方法，時間復雜度近乎線性為：O(n)。

6、希爾（Shell）排序：先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數(shù)的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量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]，待序區(qū)為R[1..n]。

(ii)循環(huán)執(zhí)行步驟3～步驟4，共n-1次。

(iii)假設為第i 運行，則待序區(qū)為R[1..n-i+1]，將堆頂元素R[1]與待序區(qū)尾元素R[n-i+1]交換，此時頂點元素被輸出，新的待序區(qū)為R[1..n-i ]。

(iv)待序區(qū)對應的堆已經(jīng)被破壞，將之重新調整為大頂堆。

（4）堆排序時間復雜度為：O(nlog2n)，是不穩(wěn)定的排序。

9、冒泡排序的基本思想是，通過相鄰元素之間的比較和交換，將排序碼較小的元素逐漸從底部移向頂部。由于整個排序的過程就像水底下的氣泡一樣逐漸向上冒，因此稱為冒泡算法。

10、快速排序采用的是分治法，其基本思想是將原問題分解成若干個規(guī)模更小但結構與原問題相似的子問題。通過遞歸地解決這些子問題，然后再將這些子問題的解組合成原問題的解。

快速排序通常包括兩個步驟：

第一步，在待排序的n個記錄中任取一個記錄，以該記錄的排序碼為準，將所有記錄都分成兩組，第1組都小于該數(shù)，第2組都大于該數(shù)，如圖所示。

第二步，采用相同的方法對左、右兩組分別進行排序，直到所有記錄都排到相應的位置為止。

11、歸并也稱為合并，是將兩個或兩個以上的有序子表合并成一個新的有序表。若將兩個有序表合并成一個有序表，則稱為二路合并。合并的過程是：比較A[i]和A[j]的排序碼大小，若A[i]的排序碼小于等于A[j]的排序碼，則將第一個有序表中的元素A[i]復制到R[k]中，并令i和k分別加1；如此循環(huán)下去，直到其中一個有序表比較和復制完，然后再將另一個有序表的剩余元素復制到R中。

12、基數(shù)排序是一種借助多關鍵字排序思想對單邏輯關鍵字進行排序的方法?；鶖?shù)排序不是基于關鍵字比較的排序方法，它適合于元素很多而關鍵字較少的序列。基數(shù)的選擇和關鍵字的分解是根據(jù)關鍵字的類型來決定的，例如關鍵字是十進制數(shù)，則按個位、十位來分解。

【備考點撥】

1、掌握順序查找的相關概念；

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

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

4、掌握常見排序方法的分類、時間復雜度、空間復雜度、穩(wěn)定性等；

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