為幫助考生備考軟考軟件設(shè)計(jì)師考試，希賽小編為大家整理了2022下半年軟件設(shè)計(jì)師知識(shí)點(diǎn)：排序與查找，相信對(duì)大家備考會(huì)有幫助。

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

【考法分析】

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

時(shí)間復(fù)雜度；指出散列表查找的相關(guān)概念描述是否正確。

【要點(diǎn)分析】

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

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

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

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

若R[mid].key＞k，則由表的有序性可知R[mid,…,n].key均大于k，因此若表中存在關(guān)鍵字等于k的結(jié)點(diǎn)，則該結(jié)點(diǎn)必定是在位置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，則查找成功，算法結(jié)束。

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

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

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

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

【例題】請(qǐng)給出在含有12個(gè)元素的有序表｛1，4，10，16，17，18，23，29，33，40，50，51｝中二分查找關(guān)鍵字17的過(guò)程。

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

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

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

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

4、排序分類(lèi)

5、直接插入排序：即當(dāng)插入第i個(gè)記錄時(shí)，R1，R2，…，Ri-1均已排好序，因此，將第i個(gè)記錄Ri依次與Ri-1，…，R2，R1進(jìn)行比較，找到合適的位置插入。它簡(jiǎn)單明了，但速度很慢。

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

6、希爾（Shell）排序：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為dl的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt–l<O<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂Ｔ摲椒▽?shí)質(zhì)上是一種分組插入方法。

7、直接選擇排序的過(guò)程是，首先在所有記錄中選出排序碼最小的記錄，把它與第1個(gè)記錄交換，然后在其余的記錄內(nèi)選出排序碼最小的記錄，與第2個(gè)記錄交換……依次類(lèi)推，直到所有記錄排完為止。

8、堆排序

（1）堆的定義：設(shè)有n個(gè)元素的序列{K1，K2，…，Kn}，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱(chēng)之為堆。

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

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

其中(i)稱(chēng)為小頂堆，(ii)稱(chēng)為大頂堆。

（2）堆排序的基本思想為：先將序列建立堆，然后輸出堆頂元素，再將剩下的序列建立堆，然后再輸出堆頂元素，依此類(lèi)推，直到所有元素均輸出為止，此時(shí)元素輸出的序列就是一個(gè)有序序列。

（3）堆排序的算法步驟如下(以大頂堆為例)：

(i)初始時(shí)將順序表R[1..n]中元素建立為一個(gè)大頂堆，堆頂位于R[1]，待序區(qū)為R[1..n]。

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

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

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

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

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

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

快速排序通常包括兩個(gè)步驟：

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

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

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

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

【備考點(diǎn)撥】

1、掌握順序查找的相關(guān)概念；

2、掌握二分查找的過(guò)程；

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

4、掌握常見(jiàn)排序方法的分類(lèi)、時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性等；

5、掌握常見(jiàn)排序方法的排序過(guò)程（堆排序了解其排序過(guò)程）。