數(shù)據(jù)結(jié)構(gòu) 選擇排序_第1頁
數(shù)據(jù)結(jié)構(gòu) 選擇排序_第2頁
數(shù)據(jù)結(jié)構(gòu) 選擇排序_第3頁
數(shù)據(jù)結(jié)構(gòu) 選擇排序_第4頁
數(shù)據(jù)結(jié)構(gòu) 選擇排序_第5頁
已閱讀5頁,還剩18頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、選擇排序(選擇排序(Selection sortSelection sort) 選擇排序(選擇排序(Selection sort)是以選擇為基礎(chǔ)的一種)是以選擇為基礎(chǔ)的一種常用排序方法,從記錄的無序子序列中常用排序方法,從記錄的無序子序列中“選擇選擇”關(guān)鍵關(guān)鍵字最小或最大的記錄,并將其加入到有序子序列的一字最小或最大的記錄,并將其加入到有序子序列的一端,以增加記錄的有序子序列的長度。它也有幾種不端,以增加記錄的有序子序列的長度。它也有幾種不同的實(shí)現(xiàn)方法,這里僅介紹簡單選擇排序、樹形排序同的實(shí)現(xiàn)方法,這里僅介紹簡單選擇排序、樹形排序和堆排序。和堆排序。 1. 1. 簡單選擇排序簡單選擇排序(1)

2、算法描述)算法描述 簡單選擇排序算法的基本思路:對于一組關(guān)鍵字簡單選擇排序算法的基本思路:對于一組關(guān)鍵字(Kl,K2,Kn),將其由小到大進(jìn)行排序,將其由小到大進(jìn)行排序,首先從首先從Kl,K2,Kn中選擇最小值,假設(shè)是中選擇最小值,假設(shè)是Kk,則將,則將Kk與與K1對換;然后從對換;然后從K2,K3,Kn中選擇最小值中選擇最小值Kk+1,再將再將Kk+1與與K2對換。如此進(jìn)行選擇和調(diào)換,對第對換。如此進(jìn)行選擇和調(diào)換,對第i趟趟選擇排序,進(jìn)行選擇排序,進(jìn)行n-i次關(guān)鍵字比較,從次關(guān)鍵字比較,從n-i+1個(gè)記錄中選個(gè)記錄中選出關(guān)鍵字最小的記錄,并與第出關(guān)鍵字最小的記錄,并與第i個(gè)記錄交換。令個(gè)記錄

3、交換。令i從從1至至n-1,進(jìn)行,進(jìn)行n-1趟選擇排序,一個(gè)由小到大的有序序列就趟選擇排序,一個(gè)由小到大的有序序列就形成了。形成了。例例1 設(shè)有一組關(guān)鍵字設(shè)有一組關(guān)鍵字49,39,66,49*,76,11,27,96,這,這里里n8。試用簡單選擇排序方法,將這組記錄由小到大進(jìn)行排。試用簡單選擇排序方法,將這組記錄由小到大進(jìn)行排序。其排序過程如圖所示,序。其排序過程如圖所示,算法實(shí)現(xiàn)如下:算法實(shí)現(xiàn)如下:void SelectSort(SqList &L) /* 對順序表對順序表L作簡單選擇排序。作簡單選擇排序。*/ int i , j; RedType temp; for (i=1; i

4、L.length; +i) /* 選擇第選擇第i小的記錄并交換到位小的記錄并交換到位*/ j = SelectMinKey(L, i); /* 在在L.ri.L.length中選擇中選擇key最小最小的記錄的記錄*/ if (i!=j) /* L.riL.rj; 與第與第i個(gè)記錄交換個(gè)記錄交換*/ temp=L.ri; L.ri=L.rj; L.rj=temp; / * SelectSort*/(2)算法分析)算法分析 在簡單選擇排序中,無論待排序的記錄初始序列在簡單選擇排序中,無論待排序的記錄初始序列是否有序,都需要執(zhí)行是否有序,都需要執(zhí)行n(n-1)/2次關(guān)鍵字的比較操作。次關(guān)鍵字的比較操

5、作。如果待排序的記錄初始序列就是已經(jīng)排好序的正列,如果待排序的記錄初始序列就是已經(jīng)排好序的正列,則無須移動記錄,因?yàn)槊總€(gè)元素都位于其最終位置上則無須移動記錄,因?yàn)槊總€(gè)元素都位于其最終位置上了;而如果待排序的記錄初始序列是逆序,即在最壞了;而如果待排序的記錄初始序列是逆序,即在最壞情況下,則要做情況下,則要做3(n-1)次記錄移動。所以,簡單選擇排次記錄移動。所以,簡單選擇排序的時(shí)間復(fù)雜度是序的時(shí)間復(fù)雜度是O(n*n)。 由上面的例由上面的例1很顯然看到,很顯然看到,49在排序前位于在排序前位于49*的的前面,而經(jīng)簡單選擇排序后卻位于前面,而經(jīng)簡單選擇排序后卻位于49*后面了,它們的后面了,它們

6、的相對位置發(fā)生了顛倒,因此簡單選擇排序算法是不穩(wěn)相對位置發(fā)生了顛倒,因此簡單選擇排序算法是不穩(wěn)定排序算法。定排序算法。3. 3. 堆排序堆排序(1)堆的定義)堆的定義 堆是一個(gè)記錄序列堆是一個(gè)記錄序列k1,k2,kn,對于列表,對于列表中位置中位置i(編號從(編號從1開始)處的記錄的關(guān)鍵字開始)處的記錄的關(guān)鍵字ki,當(dāng)且僅,當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí),稱之為堆。當(dāng)滿足下列關(guān)系時(shí),稱之為堆。 kik2i 或或 kik2i kik2i+1 kik2i+1 ( i 1,2,n/2 ) 其中,每個(gè)結(jié)點(diǎn)關(guān)鍵字都不小于其子孫結(jié)點(diǎn)關(guān)鍵字其中,每個(gè)結(jié)點(diǎn)關(guān)鍵字都不小于其子孫結(jié)點(diǎn)關(guān)鍵字的堆稱為的堆稱為“大根堆大根堆”

7、;而每個(gè)結(jié)點(diǎn)關(guān)鍵字都不小于其;而每個(gè)結(jié)點(diǎn)關(guān)鍵字都不小于其子孫結(jié)點(diǎn)關(guān)鍵字的堆稱為子孫結(jié)點(diǎn)關(guān)鍵字的堆稱為“小根堆小根堆”。下面的討論中。下面的討論中以小根堆為例。以小根堆為例。 判斷下列序列是否為堆?判斷下列序列是否為堆? (100,85,98,77,80,60,82,40,20,15,67) (100,98,85,82,80,77,60,40,20,15,67) (15,20,40,60,67,77,80,82,85,98,100) 我們已經(jīng)知道,對于一棵有我們已經(jīng)知道,對于一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹,個(gè)結(jié)點(diǎn)的完全二叉樹,當(dāng)它的結(jié)點(diǎn)由上而下,自左至右編號之后,編號為當(dāng)它的結(jié)點(diǎn)由上而下,自左至右編

8、號之后,編號為1n/2的結(jié)點(diǎn)為分支結(jié)點(diǎn),編號大于的結(jié)點(diǎn)為分支結(jié)點(diǎn),編號大于n/2的結(jié)點(diǎn)為葉子結(jié)的結(jié)點(diǎn)為葉子結(jié)點(diǎn),對于每個(gè)編號為點(diǎn),對于每個(gè)編號為i的分支結(jié)點(diǎn),它的左孩子的編號為的分支結(jié)點(diǎn),它的左孩子的編號為2i,它的右孩子的編號為,它的右孩子的編號為2i+1。對于每個(gè)編號為。對于每個(gè)編號為i(i1)的結(jié)點(diǎn),它的雙親的編號為的結(jié)點(diǎn),它的雙親的編號為i/2。 因此,我們還可以借助完全二叉樹來描述堆的概念:因此,我們還可以借助完全二叉樹來描述堆的概念:若完全二叉樹中任一非葉子結(jié)點(diǎn)的值均小于等于若完全二叉樹中任一非葉子結(jié)點(diǎn)的值均小于等于(或大于或大于等于等于)其左、右孩子結(jié)點(diǎn)的值,則從根結(jié)點(diǎn)開始按結(jié)點(diǎn)

9、編其左、右孩子結(jié)點(diǎn)的值,則從根結(jié)點(diǎn)開始按結(jié)點(diǎn)編號排列所得的結(jié)點(diǎn)序列就是一個(gè)堆。號排列所得的結(jié)點(diǎn)序列就是一個(gè)堆。 (2)算法描述)算法描述 堆頂記錄對應(yīng)完全二叉樹的根結(jié)點(diǎn),堆頂記錄關(guān)鍵堆頂記錄對應(yīng)完全二叉樹的根結(jié)點(diǎn),堆頂記錄關(guān)鍵字是所有記錄關(guān)鍵字的最值,堆排序就是利用堆的上述特字是所有記錄關(guān)鍵字的最值,堆排序就是利用堆的上述特征完成排序的。在輸出堆頂?shù)淖畲螅ɑ蜃钚。┲?,使得征完成排序的。在輸出堆頂?shù)淖畲螅ɑ蜃钚。┲?,使得剩余的剩余的n-1個(gè)記錄的序列重新調(diào)整為一個(gè)堆,于是又得到個(gè)記錄的序列重新調(diào)整為一個(gè)堆,于是又得到次大(或次?。┲荡未螅ɑ虼涡。┲等绱朔磸?fù)執(zhí)行,直至所以記錄都排如此反復(fù)執(zhí)行,

10、直至所以記錄都排序?yàn)橐粋€(gè)有序序列。這就是堆排序(序?yàn)橐粋€(gè)有序序列。這就是堆排序(Heap Sort)。)。 由于初始記錄序列不一定滿足堆關(guān)系,因此堆排序由于初始記錄序列不一定滿足堆關(guān)系,因此堆排序過程大體分兩步處理:過程大體分兩步處理: 初建堆。從堆的定義出發(fā),先取初建堆。從堆的定義出發(fā),先取i=n/2 (它一定是它一定是第第n個(gè)結(jié)點(diǎn)雙親的編號個(gè)結(jié)點(diǎn)雙親的編號),將以,將以i結(jié)點(diǎn)為根的子樹調(diào)整成為堆;結(jié)點(diǎn)為根的子樹調(diào)整成為堆;然后令然后令i=i-1;再將以;再將以i結(jié)點(diǎn)為根的子樹調(diào)整成為堆。此時(shí)結(jié)點(diǎn)為根的子樹調(diào)整成為堆。此時(shí)可能會反復(fù)調(diào)整某些結(jié)點(diǎn),直到可能會反復(fù)調(diào)整某些結(jié)點(diǎn),直到i=1為止,堆

11、初建完成。為止,堆初建完成。 堆排序。首先輸出堆頂元素堆排序。首先輸出堆頂元素(一般是最小值一般是最小值),讓堆,讓堆中最后一個(gè)元素上移到原堆頂位置,然后恢復(fù)堆,因?yàn)榻?jīng)中最后一個(gè)元素上移到原堆頂位置,然后恢復(fù)堆,因?yàn)榻?jīng)過第一步輸出堆頂元素的操作后,往往破壞了原來的堆關(guān)過第一步輸出堆頂元素的操作后,往往破壞了原來的堆關(guān)系,所以要恢復(fù)堆;重復(fù)執(zhí)行輸出堆頂元素、堆尾元素上系,所以要恢復(fù)堆;重復(fù)執(zhí)行輸出堆頂元素、堆尾元素上移和恢復(fù)堆的操作,直到全部元素輸出完為止。按輸出元移和恢復(fù)堆的操作,直到全部元素輸出完為止。按輸出元素的前后次序排列,就形成了有序序列,完成了堆排序的素的前后次序排列,就形成了有序序

12、列,完成了堆排序的操作。操作。例例 設(shè)有設(shè)有n個(gè)記錄個(gè)記錄(n8)的關(guān)鍵字是的關(guān)鍵字是30,50,60,35,86,10,40,45,試用堆排序方法,將這組記錄由小到,試用堆排序方法,將這組記錄由小到大進(jìn)行排序。大進(jìn)行排序。 第一步:初始建堆,其建堆過程如圖所示。因?yàn)榈谝徊剑撼跏冀ǘ?,其建堆過程如圖所示。因?yàn)閚=8,所,所以從以從i4開始。開始。 第二步:堆排序。這是一個(gè)反復(fù)輸出堆頂元素,將堆第二步:堆排序。這是一個(gè)反復(fù)輸出堆頂元素,將堆尾元素移至堆頂,再調(diào)整恢復(fù)堆的過程?;謴?fù)堆的過程尾元素移至堆頂,再調(diào)整恢復(fù)堆的過程?;謴?fù)堆的過程與初建堆中與初建堆中i=1時(shí)所進(jìn)行的操作完全相同。時(shí)所進(jìn)行的操

13、作完全相同。 請注意:每輸出一次堆頂元素,堆尾的邏輯位置退請注意:每輸出一次堆頂元素,堆尾的邏輯位置退1,直到堆中剩下一個(gè)元素為止,排序過程如圖所示。直到堆中剩下一個(gè)元素為止,排序過程如圖所示。 輸出序列:輸出序列: 10 30 35 40 45 50 60 86 由上可知,調(diào)整恢復(fù)堆操作過程要被多次反復(fù)調(diào)用,由上可知,調(diào)整恢復(fù)堆操作過程要被多次反復(fù)調(diào)用,即當(dāng)即當(dāng)i值確定之后,以值確定之后,以ki為比較參照值,與其左、右孩子為比較參照值,與其左、右孩子的關(guān)鍵字比較和調(diào)整,使以結(jié)點(diǎn)的關(guān)鍵字比較和調(diào)整,使以結(jié)點(diǎn)i為根的子樹成為堆,因?yàn)楦淖訕涑蔀槎眩虼税汛诉^程設(shè)計(jì)成函數(shù)此把此過程設(shè)計(jì)成函數(shù)Hea

14、p:void Heap(RedType r ,int i,int m) /*i是根結(jié)點(diǎn)編號,是根結(jié)點(diǎn)編號,m是以是以i結(jié)點(diǎn)為根的子樹的最后一個(gè)結(jié)點(diǎn)編號結(jié)點(diǎn)為根的子樹的最后一個(gè)結(jié)點(diǎn)編號*/ x=ri;j=2*i;/* x保存根記錄的內(nèi)容,保存根記錄的內(nèi)容,j為左孩子編號為左孩子編號*/ while (j=m) if ( jm&rjkeyrj+1key) j+; /* 當(dāng)結(jié)點(diǎn)當(dāng)結(jié)點(diǎn)i有左、右兩個(gè)孩子時(shí),有左、右兩個(gè)孩子時(shí),j取關(guān)鍵字值較小的取關(guān)鍵字值較小的孩子結(jié)點(diǎn)編號孩子結(jié)點(diǎn)編號*/ if ( rj. keyx. key) ri=rj;i=j;j=2*i; /*向下一層探測向下一層探測*/

15、 else j=m+1; /*x. key小于左、右孩于的關(guān)鍵字,強(qiáng)制使小于左、右孩于的關(guān)鍵字,強(qiáng)制使jm,以便結(jié)束循環(huán),以便結(jié)束循環(huán)*/ ri=x; /* Heap */ 另外,還需要設(shè)計(jì)一個(gè)主體算法,使在初建堆階段,另外,還需要設(shè)計(jì)一個(gè)主體算法,使在初建堆階段,讓讓i從從n/2變化到變化到1,循環(huán)調(diào)用,循環(huán)調(diào)用heap函數(shù),而在堆排序階函數(shù),而在堆排序階段,每輸出一次堆頂元素,將堆尾元素移至堆頂之后,段,每輸出一次堆頂元素,將堆尾元素移至堆頂之后,就要調(diào)用一次就要調(diào)用一次heap函數(shù)來恢復(fù)堆。主體算法由函數(shù)函數(shù)來恢復(fù)堆。主體算法由函數(shù)Heapsort來實(shí)現(xiàn):來實(shí)現(xiàn):void Heapsor

16、t(RedType r ,int n) /* n為文件的實(shí)際記錄數(shù),為文件的實(shí)際記錄數(shù),ro沒有使用沒有使用*/ for(i=n/2;i=1;i-) Heap(r,i,n); /*初建堆初建堆*/ for(v=n; v=2; v-) x=r1; r1=rv; rv=x; /*堆頂堆尾元素對換堆頂堆尾元素對換*/ Heap(r,1,v-1); /*本次比上次少處理一個(gè)記錄本次比上次少處理一個(gè)記錄*/* Heapsort */ (3)算法分析)算法分析 在堆排序圖示例中,堆越畫越小,堆中結(jié)點(diǎn)越來越在堆排序圖示例中,堆越畫越小,堆中結(jié)點(diǎn)越來越少,實(shí)際上,在用來存儲堆的數(shù)組中堆頂元素輸出之后少,實(shí)際上,在用來存儲堆的數(shù)組中堆頂元素輸出之后并未刪除,而是與堆尾元素對換。從圖示看輸出的是一并未刪除,而是與堆尾元素對換。從圖示看輸出的是一個(gè)由小到大的升序序列,實(shí)際最后數(shù)組中記錄的關(guān)鍵字個(gè)由小到大的升序序列,實(shí)際最后數(shù)組中記錄的關(guān)鍵字從從rl. key到到rn. key是一個(gè)由大到小的降序序列。算法是一個(gè)由大到小的降序序列。算法Heap的時(shí)間復(fù)雜度與堆所對應(yīng)的完全二叉樹的樹深的時(shí)間復(fù)雜度與堆所對應(yīng)的完全二叉樹的樹深log2n相關(guān),而算法相關(guān),而算法Heapsort中對中對Heap的

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論