軟件開發(fā)技術(shù)基礎(chǔ) 第4版 課件 2.查找和排序

查找和排序查找基本概念

查找表:

由同一類數(shù)據(jù)構(gòu)成的用于查找的集合稱作查找表。查找表是具有一定存儲結(jié)構(gòu)的數(shù)據(jù)集合，比如順序表結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、樹形結(jié)構(gòu)等。查找往往根據(jù)數(shù)據(jù)元素的某個屬性進(jìn)行。例如根據(jù)學(xué)號查找某個學(xué)生記錄。這種被用于查找的元素屬性一般稱為關(guān)鍵字，它往往可以唯一標(biāo)識一個元素。

2查找基本概念靜態(tài)查找表:查找表一旦建立，在以后的查找過程中就不會改變。它所對應(yīng)的查找算法屬于靜態(tài)查找技術(shù)。動態(tài)查找表：查找表建立后，在后來的查找過程中仍會改變查找表的內(nèi)容。它所對應(yīng)的查找算法屬于動態(tài)查找技術(shù)。

3查找基本概念平均查找長度：

為了確定數(shù)據(jù)元素在查找表中的位置，需要將給定值和表中的數(shù)據(jù)元素的關(guān)鍵字進(jìn)行比較的次數(shù)的期望值。平均查找長度ASL的計算方法為：4其中：在等概率條件下（

Pi=1/n）這時平均查找長度為：1．順序查找順序查找的方法是從表的一端開始，逐一比較給定的數(shù)據(jù)key和表中數(shù)據(jù)元素的關(guān)鍵字x的值，若兩個數(shù)據(jù)一致則查找成功，同時給出該數(shù)據(jù)元素在表中的位置，否則查找失敗。5順序表查找的平均查找長度為：2．折半查找(也稱二分查找)6假定元素按關(guān)鍵字的值升序排列，折半查找的思路是將給定的數(shù)據(jù)與有序表中間位置的元素做比較，若兩者相等則查找成功；若前者小于后者則在中間位置左邊的元素中繼續(xù)查找；若前者大于后者則在中間位置右邊的元素中繼續(xù)查找。不斷重復(fù)這一過程直到查找成功，或者直到查找區(qū)間縮小為一個元素時卻仍未找到目標(biāo)，則查找失敗。

2．折半查找(也稱二分查找)7折半查找算法的步驟描述如下：①設(shè)置查找區(qū)間初值，設(shè)下界low=0，設(shè)上界high=length-1②若low≤high則計算中間位置mid=(low+high)/2③若key<data[mid]，則設(shè)high=mid-1并繼續(xù)執(zhí)行步驟②；若key>data[mid]，則設(shè)low=mid+1并繼續(xù)執(zhí)行步驟②；若key=data[mid]則查找成功，返回目標(biāo)元素位置mid+1

（位置從1計數(shù)）。④若當(dāng)low=high時，key!=data[mid]則查找失敗，返回0。

2．折半查找(也稱二分查找)西安交通大學(xué)計算機(jī)教學(xué)實(shí)驗(yàn)中心8對給定有序數(shù)列{5，6，11，17，21，23，28，30，32，40}進(jìn)行半查找算法，查找關(guān)鍵字值為30的數(shù)據(jù)元素。則查找過程如下：第1次：{5，6，11，17，21，23，28，30，32，40}

low=0mid=(0+9)/2=4high=9第2次：{5，6，11，17，21，23，28，30，32，40}

low=5mid=7high=9排序基本概念

排序的定義為：假設(shè)含n個記錄的序列為{R1，R2，…，Rn}，其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}。這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個關(guān)系Kp1≤Kp2≤…≤Kpn，按此固有關(guān)系將最初的記錄序列重新排列為{Rp1,Rp2,…，Rpn}的操作稱作排序。西安交通大學(xué)計算機(jī)教學(xué)實(shí)驗(yàn)中心9排序基本概念

排序分為內(nèi)部排序和外部排序。若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序；反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序。本節(jié)只討論內(nèi)部排序的若干方法

10排序基本概念

內(nèi)部排序方法有很多類型。按方法實(shí)現(xiàn)特點(diǎn)可分為插入排序、選擇排序、交換排序、歸并排序等等；按方法效率可分為簡單的排序法、先進(jìn)的排序法等等。簡單的排序法包括插入排序、選擇排序、冒泡排序等，它們的時間復(fù)雜度為O(n2)。而先進(jìn)的排序法包括快速排序、歸并排序等，它們的時間復(fù)雜度大約為O(nlog2n)。西安交通大學(xué)計算機(jī)教學(xué)實(shí)驗(yàn)中心111、直接插入排序

西安交通大學(xué)計算機(jī)教學(xué)實(shí)驗(yàn)中心12初始狀態(tài)：[35] 22 16 19 22第1趟：[22 35] 16 19 22第2趟：[16 22 35] 19 22第3趟：[16 19 22 35] 22第4趟：[16 19 22 22 35]直接插入排序執(zhí)行過程在序列{35，22，16，19，22}上應(yīng)用插入排序的過程，為了對序列中相同記錄加以區(qū)別，使用了下劃線。

2、簡單選擇排序西安交通大學(xué)計算機(jī)教學(xué)實(shí)驗(yàn)中心13在序列{35，22，16，19，22}上應(yīng)用簡單選擇排序的過程。

初始狀態(tài)：[35 22 16 19 22]

第1趟：[16] [22 35 19 22]

第2趟：[16 19] [35 22 22]

第3趟：[16 19 22]

[35 22]

第4趟：[16 19 22 22] [35]3、冒泡排序西安交通大學(xué)計算機(jī)教學(xué)實(shí)驗(yàn)中心14基本思路：第一趟排序?qū)θ坑涗汻1，R2，…，Rn自左向右順次兩兩比較，若Rk大于Rk+1則交換Rk和Rk+1(k=1,2,…,n-1)，第一趟排序完成后Rn成為序列中最大記錄。第二趟排序?qū)π蛄星皀-1個記錄采用同樣的比較和交換方法，第二趟排序完成后Rn-1成為序列中僅比Rn小的次大的記錄。第三趟排序?qū)π蛄星皀-2個記錄采用同樣處理方法。如此做下去，最多做n-1趟排序，整個序列就排序完成。3、冒泡排序西安交通大學(xué)計算機(jī)教學(xué)實(shí)驗(yàn)中心15

下圖顯示了在序列{35，22，16，19，22}上應(yīng)用冒泡排序的過程。

初始狀態(tài)：3522 16 19 [22

第1趟：2216 19 22 [35]

第2趟：1619 22 [22

[35]

第3趟：1619 [22

22 [35]

第4趟：16[19

22 22 [35]4、快速排序西安交通大學(xué)計算機(jī)教學(xué)實(shí)驗(yàn)中心16任取待排序序列中某個記錄S(例如第一個記錄)作為基準(zhǔn)，經(jīng)過比較和交換，將整個序列劃分為如下形式：{左側(cè)子序列}S{右側(cè)子序列}并且滿足：

①左側(cè)子序列中所有記錄的關(guān)鍵字都小于或等于S的關(guān)鍵字。②右側(cè)子序列中所有記錄的關(guān)鍵字都大于或等于S的關(guān)鍵字。然后分別對左右兩個子序列重復(fù)執(zhí)行上述過程，直到排序完成4、快速排序西安交通大學(xué)計算機(jī)教學(xué)實(shí)驗(yàn)中心17

在{22,35,27,16,45,19,22}上應(yīng)用劃分算法（即一趟快速排序）4、快速排序西安交通大學(xué)計算機(jī)教學(xué)實(shí)驗(yàn)中心18

當(dāng)22的位置已經(jīng)確定后，只需對{19，16}和{27,45,35,22}分別排序即可?？煞謩e取19和27為基準(zhǔn)元素。

{22，35，27，16，45，19，22}

{19，16}22{27，45，35，22}