第8章 排序技術(shù)(新).ppt_第1頁(yè)
第8章 排序技術(shù)(新).ppt_第2頁(yè)
第8章 排序技術(shù)(新).ppt_第3頁(yè)
第8章 排序技術(shù)(新).ppt_第4頁(yè)
第8章 排序技術(shù)(新).ppt_第5頁(yè)
已閱讀5頁(yè),還剩105頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

1、第八章 排序,本章的基本內(nèi)容是: 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序,概 述,排序:給定一組記錄的集合r1, r2, , rn,其相應(yīng)的關(guān)鍵碼分別為k1, k2, , kn,排序是將這些記錄排列成順序?yàn)閞s1, rs2, , rsn的一個(gè)序列,使得相應(yīng)的關(guān)鍵碼滿(mǎn)足ks1ks2ksn(稱(chēng)為升序)或ks1ks2ksn(稱(chēng)為降序)。 正序:待排序序列中的記錄已按關(guān)鍵碼排好序。 逆序(反序):待排序序列中記錄的排列順序與排好序的順序正好相反。,排序的基本概念,排序算法的穩(wěn)定性:假定在待排序的記錄集中,存在多個(gè)具有相同鍵值的記錄,若經(jīng)過(guò)排序,這些記錄的相對(duì)次序仍然保持不變,即在原序列

2、中,ki=kj且ri在rj之前,而在排序后的序列中,ri仍在rj之前,則稱(chēng)這種排序算法是穩(wěn)定的;否則稱(chēng)為不穩(wěn)定的。,概 述,排序的基本概念,概 述,排序的基本概念,單鍵排序:根據(jù)一個(gè)關(guān)鍵碼進(jìn)行的排序; 多鍵排序:根據(jù)多個(gè)關(guān)鍵碼進(jìn)行的排序。,按學(xué)號(hào)排序單鍵排序 按成績(jī)(高數(shù)英語(yǔ)思想品德)排序多鍵排序,概 述,排序的基本概念,設(shè)關(guān)鍵碼分別為k1, k2, , km,多鍵排序有兩種方法: 依次對(duì)記錄進(jìn)行m次排序,第一次按k1排序,第二次按k2排序,依此類(lèi)推。這種方法要求各趟排序所用的算法是穩(wěn)定的; 將關(guān)鍵碼k1, k2, , km分別視為字符串依次首尾連接在一起,形成一個(gè)新的字符串,然后,對(duì)記錄序列

3、按新形成的字符串排序。,排序的分類(lèi) 1. 內(nèi)排序:在排序的整個(gè)過(guò)程中,待排序的所有記錄全部被放置在內(nèi)存中 2. 外排序:由于待排序的記錄個(gè)數(shù)太多,不能同時(shí)放置在內(nèi)存,而需要將一部分記錄放置在內(nèi)存,另一部分記錄放置在外存上,整個(gè)排序過(guò)程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。,概 述,排序的基本概念,1. 基本操作。內(nèi)排序在排序過(guò)程中的基本操作: 比較:關(guān)鍵碼之間的比較; 移動(dòng):記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。 2. 輔助存儲(chǔ)空間。 輔助存儲(chǔ)空間是指在數(shù)據(jù)規(guī)模一定的條件下,除了存放待排序記錄占用的存儲(chǔ)空間之外,執(zhí)行算法所需要的其他存儲(chǔ)空間。 3.算法本身的復(fù)雜程度。,排序算法的性能,概

4、述,排序算法的存儲(chǔ)結(jié)構(gòu),概 述,從操作角度看,排序是線(xiàn)性結(jié)構(gòu)的一種操作,待排序記錄可以用順序存儲(chǔ)結(jié)構(gòu)或鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。,假定2:將待排序的記錄序列排序?yàn)樯蛐蛄小?int rn+1; /待排序記錄存儲(chǔ)在r1rn,r0留做他用,假定1:采用順序存儲(chǔ)結(jié)構(gòu),關(guān)鍵碼為整型,且記錄只有關(guān)鍵碼一個(gè)數(shù)據(jù)項(xiàng)。,插入排序,插入排序的主要操作是插入,其基本思想是:每次將一個(gè)待排序的記錄按其關(guān)鍵碼的大小插入到一個(gè)已經(jīng)排好序的有序序列中,直到全部記錄排好序?yàn)橹埂?基本思想:在插入第 i(i1)個(gè)記錄時(shí),前面的 i-1個(gè)記錄已經(jīng)排好序。,直接插入排序,插入排序,基本思想:在插入第 i(i1)個(gè)記錄時(shí),前面的 i-1個(gè)

5、記錄已經(jīng)排好序。,(1)如何構(gòu)造初始的有序序列? (2)如何查找待插入記錄的插入位置?,直接插入排序,插入排序,需解決的關(guān)鍵問(wèn)題?,直接插入排序過(guò)程示例,r 0 1 2 3 4 5 6,21,18,25,22,10,25*,21,插入排序,22,10,25,21,18,r0的作用?,暫存單元,監(jiān)視哨,解決方法: 將第1個(gè)記錄看成是初始有序表,然后從第2個(gè)記錄起依次插入到這個(gè)有序表中,直到將第n個(gè)記錄插入。,插入排序,關(guān)鍵問(wèn)題(1)如何構(gòu)造初始的有序序列?,算法描述: for (i=2; i=n; i+) 插入第i個(gè)記錄,即第i趟直接插入排序; ,關(guān)鍵問(wèn)題(2)如何查找待插入記錄的插入位置?,解

6、決方法: 在i-1個(gè)記錄的有序區(qū)r1 ri-1中插入記錄ri,首先順序查找ri的正確插入位置,然后將ri插入到相應(yīng)位置。,r0有兩個(gè)作用: 1. 進(jìn)入循環(huán)之前暫存了ri的值,使得不致于因記錄的后移而丟失ri的內(nèi)容; 2. 在查找插入位置的循環(huán)中充當(dāng)哨兵。,插入排序,算法描述: r0=ri; j=i-1; while (r0rj) rj+1=rj; j-; ,void insertSort (int r , int n) for (i=2; i=n; i+) r0=ri; j=i-1; while (r0rj) rj+1=rj; j=j-1; rj+1=r0; ,直接插入排序算法,插入排序,直接

7、插入排序算法性能分析,最好情況下(正序):,插入排序,時(shí)間復(fù)雜度為O(n)。,直接插入排序算法性能分析,插入排序,最好情況下(正序):,最壞情況下(逆序或反序):,時(shí)間復(fù)雜度為O(n2)。,時(shí)間復(fù)雜度為O(n)。,平均情況下(隨機(jī)排列):,直接插入排序算法性能分析,插入排序,時(shí)間復(fù)雜度為O(n2)。,空間性能:需要一個(gè)記錄的輔助空間。 直接插入排序算法是一種穩(wěn)定的排序算法。,直接插入排序算法性能分析,插入排序,直接插入排序算法簡(jiǎn)單、容易實(shí)現(xiàn),適用于待排序記錄基本有序或待排序記錄較小時(shí)。 當(dāng)待排序的記錄個(gè)數(shù)較多時(shí),大量的比較和移動(dòng)操作使直接插入排序算法的效率降低。,插入排序,如何改進(jìn)直接插入排序

8、?,注意到,在插入第 i(i1)個(gè)記錄時(shí),前面的 i-1 個(gè)記錄已經(jīng)排好序,則在尋找插入位置時(shí),可以用折半查找來(lái)代替順序查找,從而較少比較次數(shù)。,請(qǐng)同學(xué)們寫(xiě)出這個(gè)改進(jìn)的直接插入排序算法,并分析時(shí)間性能。,希爾排序,改進(jìn)的著眼點(diǎn): (1)若待排序記錄按關(guān)鍵碼基本有序時(shí),直接插入排序的效率可以大大提高; (2)由于直接插入排序算法簡(jiǎn)單,則在待排序記錄數(shù)量n較小時(shí)效率也很高。,插入排序,(1)應(yīng)如何分割待排序記錄,才能保證整個(gè)序列逐步向基本有序發(fā)展? (2)子序列內(nèi)如何進(jìn)行直接插入排序?,插入排序,需解決的關(guān)鍵問(wèn)題?,基本思想:將整個(gè)待排序記錄分割成若干個(gè)子序列,在子序列內(nèi)分別進(jìn)行直接插入排序,待整

9、個(gè)序列中的記錄基本有序時(shí),對(duì)全體記錄進(jìn)行直接插入排序。,希爾排序,基本有序:接近正序,例如1, 2, 8, 4, 5, 6, 7, 3, 9; 局部有序:部分有序,例如6, 7, 8, 9, 1, 2, 3, 4, 5。 局部有序不能提高直接插入排序算法的時(shí)間性能。,插入排序,希爾排序,分割待排序記錄的目的?,1. 減少待排序記錄個(gè)數(shù); 2. 使整個(gè)序列向基本有序發(fā)展。,子序列的構(gòu)成不能是簡(jiǎn)單地“逐段分割”,而是將相距某個(gè)“增量”的記錄組成一個(gè)子序列。,啟示?,希爾插入排序過(guò)程示例,1 2 3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,插入排序,30,08,13,

10、解決方法: 將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。 增量應(yīng)如何?。?希爾最早提出的方法是d1=n/2,di+1=di/2。,關(guān)鍵問(wèn)題(1)應(yīng)如何分割待排序記錄?,插入排序,算法描述: for (d=n/2; d=1; d=d/2) 以d為增量,進(jìn)行組內(nèi)直接插入排序; ,解決方法: 在插入記錄ri時(shí),自ri-d起往前跳躍式(跳躍幅度為d)搜索待插入位置,并且r0只是暫存單元,不是哨兵。當(dāng)搜索位置0,表示插入位置已找到。 在搜索過(guò)程中,記錄后移也是跳躍d個(gè)位置。 在整個(gè)序列中,前d個(gè)記錄分別是d個(gè)子序列中的第一個(gè)記錄,所以從第d+1個(gè)記錄開(kāi)始進(jìn)行插入。,插入排序,關(guān)鍵問(wèn)題(2)子序列內(nèi)如何進(jìn)行直

11、接插入排序?,算法描述:,for (i=d+1; i0 ,插入排序,關(guān)鍵問(wèn)題(2)子序列內(nèi)如何進(jìn)行直接插入排序?,希爾排序算法的時(shí)間性能,希爾排序算法的時(shí)間性能是所取增量的函數(shù),而到目前為止尚未有人求得一種最好的增量序列。 研究表明,希爾排序的時(shí)間性能在O(n2)和O(nlog2n)之間。當(dāng)n在某個(gè)特定范圍內(nèi),希爾排序所需的比較次數(shù)和記錄的移動(dòng)次數(shù)約為O(n1.3 ) 。,插入排序,希爾排序開(kāi)始時(shí)增量較大,每個(gè)子序列中的記錄個(gè)數(shù)較少,從而排序速度較快;當(dāng)增量較小時(shí),雖然每個(gè)子序列中記錄個(gè)數(shù)較多,但整個(gè)序列已基本有序,排序速度也較快。,交換排序的主要操作是交換,其主要思想是:在待排序列中選兩個(gè)記

12、錄,將它們的關(guān)鍵碼相比較,如果反序(即排列順序與排序后的次序正好相反),則交換它們的存儲(chǔ)位置。,交換排序,反序則 交換,起泡排序,基本思想:兩兩比較相鄰記錄的關(guān)鍵碼,如果反序則交換,直到?jīng)]有反序的記錄為止。,交換排序,05,98,12,69,38,53,81,起泡排序過(guò)程示例,交換排序, 在一趟起泡排序中,若有多個(gè)記錄位于最終位置,應(yīng)如何記載? 如何確定起泡排序的范圍,使得已經(jīng)位于最終位置的記錄不參與下一趟排序? 如何判別起泡排序的結(jié)束?,交換排序,需解決的關(guān)鍵問(wèn)題?,起泡排序,解決方法: 設(shè)變量exchange記載記錄交換的位置,則一趟排序后,exchange記載的一定是這一趟排序中記錄的最

13、后一次交換的位置,且從此位置以后的所有記錄均已經(jīng)有序。,交換排序,關(guān)鍵問(wèn)題:如何記載一趟排序過(guò)程中交換的多個(gè)記錄?,交換排序,關(guān)鍵問(wèn)題:如何記載一趟排序過(guò)程中交換的多個(gè)記錄?,算法描述: if (rjrj+1) rjrj+1; exchange=j; ,解決方法: 設(shè)變量exchange記載記錄交換的位置,則一趟排序后,exchange記載的一定是這一趟排序中記錄的最后一次交換的位置,且從此位置以后的所有記錄均已經(jīng)有序。,解決方法: 設(shè)bound位置的記錄是無(wú)序區(qū)的最后一個(gè)記錄,則每趟起泡排序的范圍是r1 rbound。 在一趟排序后,從exchange位置之后的記錄一定是有序的,所以boun

14、d=exchange。,交換排序,關(guān)鍵問(wèn)題:如何確定起泡排序的范圍?,解決方法: 設(shè)bound位置的記錄是無(wú)序區(qū)的最后一個(gè)記錄,則每趟起泡排序的范圍是r1 rbound。 在一趟排序后,從exchange位置之后的記錄一定是有序的,所以bound=exchange。,交換排序,關(guān)鍵問(wèn)題:如何確定起泡排序的范圍?,算法描述: bound=exchange; for (j=1; jrj+1) rjrj+1; exchange=j; ,解決方法: 在每一趟起泡排序之前,令exchange的初值為0,在以后的排序過(guò)程中,只要有記錄交換,exchange的值就會(huì)大于0。這樣,在一趟比較完畢,就可以通過(guò)e

15、xchange的值是否為0來(lái)判別是否有記錄交換,從而判別整個(gè)起泡排序的結(jié)束。,交換排序,關(guān)鍵問(wèn)題:如何判別起泡排序的結(jié)束?,解決方法: 在每一趟起泡排序之前,令exchange的初值為0,在以后的排序過(guò)程中,只要有記錄交換,exchange的值就會(huì)大于0。這樣,在一趟比較完畢,就可以通過(guò)exchange的值是否為0來(lái)判別是否有記錄交換,從而判別整個(gè)起泡排序的結(jié)束。,交換排序,關(guān)鍵問(wèn)題:如何判別起泡排序的結(jié)束?,算法描述: while (exchange) 執(zhí)行一趟起泡排序; ,void BubbleSort(int r , int n) exchange=n; while (exchange)

16、 bound=exchange; exchange=0; for (j=1; jrj+1) rjrj+1; exchange=j; ,起泡排序算法,交換排序,起泡排序的時(shí)間性能分析,最好情況(正序):,交換排序,時(shí)間復(fù)雜度為O(n)。,最壞情況(反序):,起泡排序的時(shí)間性能分析,最好情況(正序):,交換排序,時(shí)間復(fù)雜度為O(n);,時(shí)間復(fù)雜度為O(n2)。,平均情況:時(shí)間復(fù)雜度為O(n2)。,交換排序,如何改進(jìn)起泡排序?,造成不對(duì)稱(chēng)的原因是什么?,交換排序,如何改變不對(duì)稱(chēng)性?,在排序過(guò)程中交替改變掃描方向雙向起泡排序,快速排序,改進(jìn)的著眼點(diǎn):在起泡排序中,記錄的比較和移動(dòng)是在相鄰單元中進(jìn)行的,

17、記錄每次交換只能上移或下移一個(gè)單元,因而總的比較次數(shù)和移動(dòng)次數(shù)較多。,交換排序,減少總的比較次數(shù)和移動(dòng)次數(shù),增大記錄的比較和移動(dòng)距離,較大記錄從前面直接移動(dòng)到后面 較小記錄從后面直接移動(dòng)到前面,快速排序的基本思想,首先選一個(gè)軸值(即比較的基準(zhǔn)),通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分,前一部分記錄的關(guān)鍵碼均小于或等于軸值,后一部分記錄的關(guān)鍵碼均大于或等于軸值,然后分別對(duì)這兩部分重復(fù)上述方法,直到整個(gè)序列有序。,交換排序,如何選擇軸值? 如何實(shí)現(xiàn)分割(稱(chēng)一次劃分)? 如何處理分割得到的兩個(gè)待排序子序列? 如何判別快速排序的結(jié)束?,需解決的關(guān)鍵問(wèn)題?,選擇軸值的方法: 1.使用第一個(gè)記錄的關(guān)鍵

18、碼; 2.選取序列中間記錄的關(guān)鍵碼; 3.比較序列中第一個(gè)記錄、最后一個(gè)記錄和中間記錄的關(guān)鍵碼,取關(guān)鍵碼居中的作為軸值并調(diào)換到第一個(gè)記錄的位置; 4.隨機(jī)選取軸值。,交換排序,關(guān)鍵問(wèn)題:如何選擇軸值?,選取不同軸值的后果: 決定兩個(gè)子序列的長(zhǎng)度,子序列的長(zhǎng)度最好相等。,13,65,27,50,38,49,55,交換排序,關(guān)鍵問(wèn)題:如何實(shí)現(xiàn)一次劃分?,解決方法: 設(shè)待劃分的序列是rs rt,設(shè)參數(shù)i,j分別指向子序列左、右兩端的下標(biāo)s和t,令rs為軸值, (1)j從后向前掃描,直到rjri,將rj移動(dòng)到ri的位置,使關(guān)鍵碼?。ㄍS值相比)的記錄移動(dòng)到前面去; (2)i從前向后掃描,直到rirj,

19、將ri移動(dòng)到rj的位置,使關(guān)鍵碼大(同軸值比較)的記錄移動(dòng)到后面去; (3)重復(fù)上述過(guò)程,直到i=j。,交換排序,關(guān)鍵問(wèn)題:如何實(shí)現(xiàn)一次劃分?,交換排序,關(guān)鍵問(wèn)題:如何實(shí)現(xiàn)一次劃分?,算法描述:,int Partition(int r , int first, int end) i=first; j=end; /初始化 while (ij) while (ij /i為軸值記錄的最終位置 ,解決方法: 對(duì)分割得到的兩個(gè)子序列遞歸地執(zhí)行快速排序。,交換排序,關(guān)鍵問(wèn)題:如何處理分割得到的兩個(gè)待排序子序列?,38,算法描述:,交換排序,關(guān)鍵問(wèn)題:如何處理分割得到的兩個(gè)待排序子序列?,void Quic

20、kSort (int r , int first, int end ) pivotpos = Partition (r, first, end ); /一次劃分 QuickSort (r, first, pivotpos-1); /對(duì)前一個(gè)子序列進(jìn)行快速排序 QuickSort (r, pivotpos+1, end ); /對(duì)后一個(gè)子序列進(jìn)行快速排序 ,解決方法: 若待排序列中只有一個(gè)記錄,顯然已有序,否則進(jìn)行一次劃分后,再分別對(duì)分割所得的兩個(gè)子序列進(jìn)行快速排序(即遞歸處理)。,交換排序,關(guān)鍵問(wèn)題:如何判別快速排序的結(jié)束?,void QuickSort (int r , int first,

21、 int end ) /在序列 firstend中遞歸地進(jìn)行快速排序 if (first end) pivotpos = Partition (r, first, end ); QuickSort (r, first, pivotpos-1); QuickSort (r, pivotpos+1, end ); ,算法描述:,交換排序,關(guān)鍵問(wèn)題:如何判別快速排序的結(jié)束?,交換排序,例:38, 27, 55, 50, 13, 49, 65的快速排序遞歸樹(shù)如下:,快速排序的遞歸執(zhí)行過(guò)程可以用遞歸樹(shù)描述。,快速排序的時(shí)間性能分析,快速排序的時(shí)間性能分析,交換排序,快速排序的時(shí)間性能,快速排序遞歸的深度

22、,每次劃分軸值的選取,最好情況: 每一次劃分對(duì)一個(gè)記錄定位后,該記錄的左側(cè)子表與右側(cè)子表的長(zhǎng)度相同,為O(nlog2n)。,快速排序的時(shí)間性能分析,交換排序,T(n)2T(n/2)n 2(2T(n/4)n/2)n4T(n/4)2n 4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n),最壞情況: 每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列(另一個(gè)子序列為空),為 O(n2)。,最好情況: 每一次劃分對(duì)一個(gè)記錄定位后,該記錄的左側(cè)子表與右側(cè)子表的長(zhǎng)度相同,為O(nlog2n)。,快速排序的時(shí)間性能分析,交換排序,平均情況:為O(nlog2n)。,選擇排

23、序的主要操作是選擇,其主要思想是:每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄,添加到有序序列中。,選擇排序,簡(jiǎn)單選擇排序,基本思想:第i 趟在n-i+1(i=1,2,n-1)個(gè)記錄中選取關(guān)鍵碼最小的記錄作為有序序列中的第i個(gè)記錄。,選擇排序,需解決的關(guān)鍵問(wèn)題?,如何在待排序序列中選出關(guān)鍵碼最小的記錄? 如何確定待排序序列中關(guān)鍵碼最小的記錄在有序序列中的位置?,簡(jiǎn)單選擇排序示例,i = 2,最小者 08 交換21,08,最小者 16 交換25,16,最小者 21 交換49,21,21,28,i = 1,25,16,49,08,08,i = 3,21,選擇排序,16,i = 4,最小者 25

24、交換25,28,i = 5,最小者 28 不交換,選擇排序,簡(jiǎn)單選擇排序示例,25,28,無(wú)序區(qū)只有 一個(gè)記錄,解決方法: 設(shè)置一個(gè)整型變量index,用于記錄在一趟比較的過(guò)程中關(guān)鍵碼最小的記錄位置。,選擇排序,關(guān)鍵問(wèn)題:如何在無(wú)序區(qū)中選出關(guān)鍵碼最小的記錄?,21,28,25,16,49,08,index,index,08,算法描述: index=i; for (j=i+1; j=n; j+) if (rjrindex) index=j;,解決方法: 設(shè)置一個(gè)整型變量index,用于記錄在一趟比較的過(guò)程中關(guān)鍵碼最小的記錄位置。,關(guān)鍵問(wèn)題:如何在無(wú)序區(qū)中選出關(guān)鍵碼最小的記錄?,解決方法: 第i趟

25、簡(jiǎn)單選擇排序的待排序區(qū)間是ri rn,則ri是無(wú)序區(qū)第一個(gè)記錄,所以,將index所記載的關(guān)鍵碼最小的記錄與ri交換。,選擇排序,關(guān)鍵問(wèn)題:如何確定最小記錄的最終位置?,算法描述: if (index!=i) ririndex;,void selectSort ( int r , int n) for ( i=1; irindex; ,簡(jiǎn)單選擇排序算法,選擇排序,簡(jiǎn)單選擇排序算法的性能分析,移動(dòng)次數(shù): 最好情況(正序):0次,選擇排序,1,2,3,4,最壞情況:3(n-1)次,簡(jiǎn)單選擇排序算法的性能分析,移動(dòng)次數(shù): 最好情況(正序):0次,選擇排序,空間性能:需一個(gè)輔助空間。 穩(wěn)定性:是一種不

26、穩(wěn)定的排序算法。,1,2,3,4,比較次數(shù):,簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為O(n2)。,堆排序,改進(jìn)的著眼點(diǎn):如何減少關(guān)鍵碼間的比較次數(shù)。若能利用每趟比較后的結(jié)果,也就是在找出鍵值最小記錄的同時(shí),也找出鍵值較小的記錄,則可減少后面的選擇中所用的比較次數(shù),從而提高整個(gè)排序過(guò)程的效率。,選擇排序,減少關(guān)鍵碼間的比較次數(shù),查找最小值的同時(shí),找出較小值,堆的定義,堆是具有下列性質(zhì)的完全二叉樹(shù):每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值(稱(chēng)為小根堆),或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值(稱(chēng)為大根堆)。,選擇排序,1. 小根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最小者。 2. 較小結(jié)點(diǎn)靠近根結(jié)點(diǎn),但不絕對(duì)。,堆的

27、定義,堆是具有下列性質(zhì)的完全二叉樹(shù):每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值(稱(chēng)為小根堆),或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值(稱(chēng)為大根堆)。,選擇排序,1. 大根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最大者。 2. 較大結(jié)點(diǎn)靠近根結(jié)點(diǎn),但不絕對(duì)。,堆和序列的關(guān)系,選擇排序,將堆用順序存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ),則堆對(duì)應(yīng)一組序列。,基本思想:首先將待排序的記錄序列構(gòu)造成一個(gè)堆,此時(shí),選出了堆中所有記錄的最大者,然后將它從堆中移走,并將剩余的記錄再調(diào)整成堆,這樣又找出了次小的記錄,以此類(lèi)推,直到堆中只有一個(gè)記錄。,選擇排序,堆排序,需解決的關(guān)鍵問(wèn)題?,如何由一個(gè)無(wú)序序列建成一個(gè)堆(即初始建堆)? 如何處理堆頂記

28、錄? 如何調(diào)整剩余記錄,成為一個(gè)新堆(即重建堆)?,堆調(diào)整,堆調(diào)整:在一棵完全二叉樹(shù)中,根結(jié)點(diǎn)的左右子樹(shù)均是堆,如何調(diào)整根結(jié)點(diǎn),使整個(gè)完全二叉樹(shù)成為一個(gè)堆?,選擇排序,void sift ( int r , int k, int m ) /要篩選結(jié)點(diǎn)的編號(hào)為k,堆中最后一個(gè)結(jié)點(diǎn)的編號(hào)為m i=k; j=2*i; temp=ri; /將篩選記錄暫存 while (jrj) break; else ri=rj; i=j; j=2*i; ri=temp; /將篩選記錄移到正確位置 ,選擇排序,堆調(diào)整算法描述:,選擇排序,關(guān)鍵問(wèn)題:如何由一個(gè)無(wú)序序列建成一個(gè)堆?,算法描述: for (i=n/2; i

29、=1; i-) sift(r, i, n) ;,選擇排序,關(guān)鍵問(wèn)題:如何由一個(gè)無(wú)序序列建成一個(gè)堆?,最后一個(gè)結(jié)點(diǎn)(葉子)的序號(hào)是n, 則最后一個(gè)分支結(jié)點(diǎn)即為結(jié)點(diǎn)n的雙親, 其序號(hào)是n/2。,選擇排序,關(guān)鍵問(wèn)題:如何處理堆頂記錄?,對(duì) 應(yīng),對(duì) 應(yīng),算法描述: r1rn-i+1;,選擇排序,關(guān)鍵問(wèn)題:如何處理堆頂記錄?,解決方法: 第 i 次處理堆頂是將堆頂記錄r1與序列中第n-i+1個(gè)記錄rn-i+1交換。,選擇排序,關(guān)鍵問(wèn)題:如何調(diào)整剩余記錄,成為一個(gè)新堆?,解決方法: 第 i 次調(diào)整剩余記錄,此時(shí),剩余記錄有n-i個(gè),調(diào)整根結(jié)點(diǎn)至第n-i個(gè)記錄。,選擇排序,關(guān)鍵問(wèn)題:如何調(diào)整剩余記錄,成為一

30、個(gè)新堆?,算法描述: sift(r, 1, n-i);,堆排序算法,void HeapSort ( int r, int n) for (i=n/2; i=1; i-) /初建堆 sift(r, i, n) ; for (i=1; in; i+ ) r1rn-i+1; /移走堆頂 sift(r, 1, n-i); /重建堆 ,選擇排序,堆排序算法的性能分析,第1個(gè)for循環(huán)是初始建堆,需要O(n)時(shí)間; 第2個(gè)for循環(huán)是輸出堆頂重建堆,共需要取n-1次堆頂記錄,第 i 次取堆頂記錄重建堆需要O(log2i)時(shí)間,需要O(nlog2n)時(shí)間; 因此整個(gè)時(shí)間復(fù)雜度為O(nlog2n),這是堆排序

31、的最好、最壞和平均的時(shí)間代價(jià)。,選擇排序,歸并排序,歸并排序的主要操作是歸并,其主要思想是:將若干有序序列逐步歸并,最終得到一個(gè)有序序列。,歸并排序,歸并:將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有序序列的過(guò)程。,基本思想:將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長(zhǎng)度為1的有序序列,然后進(jìn)行兩兩歸并,得到n/2個(gè)長(zhǎng)度為2的有序序列,再進(jìn)行兩兩歸并,得到n/4個(gè)長(zhǎng)度為4的有序序列,直至得到一個(gè)長(zhǎng)度為n的有序序列為止。,二路歸并排序,歸并排序,需解決的關(guān)鍵問(wèn)題?,如何將兩個(gè)有序序列合成一個(gè)有序序列? 怎樣完成一趟歸并? 如何控制二路歸并的結(jié)束?,關(guān)鍵問(wèn)題:如何將兩個(gè)有序序列合成一個(gè)有序序列?,歸并排序

32、,60 20 31 5 44 55 65,5,20,31,60,關(guān)鍵問(wèn)題:如何將兩個(gè)有序序列合成一個(gè)有序序列?,歸并排序,60 20 31 5 44 55 65,5,20,31,60,歸并可以就地進(jìn)行嗎?,在歸并過(guò)程中,可能會(huì)破壞原來(lái)的有序序列,所以,將歸并的結(jié)果存入另外一個(gè)數(shù)組中。,關(guān)鍵問(wèn)題:如何將兩個(gè)有序序列合成一個(gè)有序序列?,歸并排序,60 20 31 5 44 55 65,5,20,31,60,關(guān)鍵問(wèn)題:如何將兩個(gè)有序序列合成一個(gè)有序序列?,歸并排序,60 20 31 5 44 55 65,5,20,31,60,子序列的長(zhǎng)度一定相等嗎?,關(guān)鍵問(wèn)題:如何將兩個(gè)有序序列合成一個(gè)有序序列?,

33、歸并排序,60 20 31 5 44 55 65,5,20,31,60,關(guān)鍵問(wèn)題:如何將兩個(gè)有序序列合成一個(gè)有序序列?,歸并排序,設(shè)相鄰的有序序列為rs rm和rm+1 rt,歸并成一個(gè)有序序列r1s r1t,void Merge (int r , int r1 , int s, int m, int t ) i=s; j=m+1; k=s; while (i=m /后一個(gè)子序列 ,歸并排序,關(guān)鍵問(wèn)題:如何將兩個(gè)有序序列合成一個(gè)有序序列?,算法描述:,歸并排序,關(guān)鍵問(wèn)題:怎樣完成一趟歸并?,60 20 31 5 44 55 65,在一趟歸并中,除最后一個(gè)有序序列外,其它有序序列中記錄的個(gè)數(shù)相同

34、,用長(zhǎng)度h表示。,歸并排序,關(guān)鍵問(wèn)題:怎樣完成一趟歸并?,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄,歸并的步長(zhǎng)是2h, 在歸并過(guò)程中,有以下三種情況:,若in-2h+1,則相鄰兩個(gè)有序表的長(zhǎng)度均為h,執(zhí)行一次歸并,完成后i加2h,準(zhǔn)備進(jìn)行下一次歸并;,i=1 n-2h+1=4,歸并排序,關(guān)鍵問(wèn)題:怎樣完成一趟歸并?,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄,歸并的步長(zhǎng)是2h,在歸并過(guò)程中,有以下三種情況:,若in-2h+1,則相鄰兩個(gè)有序表的長(zhǎng)度均為h,執(zhí)行一次歸并,完成后i加2h,準(zhǔn)備進(jìn)行下一次歸并;,算法描述: while (in-2h+1) Merge (r, r1, i, i+h-1, i+2*h

35、-1); i+=2*h; ,歸并排序,關(guān)鍵問(wèn)題:怎樣完成一趟歸并?,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄,歸并的步長(zhǎng)是2h,在歸并過(guò)程中,有以下三種情況:,若in-h+1,則表示仍有兩個(gè)相鄰有序表,一個(gè)長(zhǎng)度為h,另一個(gè)長(zhǎng)度小于h,則執(zhí)行兩個(gè)有序表的歸并,完成后退出一趟歸并。,i=4 n-2h+1=4 n-h+1=6,歸并排序,關(guān)鍵問(wèn)題:怎樣完成一趟歸并?,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄,歸并的步長(zhǎng)是2h,在歸并過(guò)程中,有以下三種情況:,若in-h+1,則表示仍有兩個(gè)相鄰有序表,一個(gè)長(zhǎng)度為h,另一個(gè)長(zhǎng)度小于h,則執(zhí)行兩個(gè)有序表的歸并,完成后退出一趟歸并。,算法描述: if (in-h+1) Merge (r, r1, i, i+h-1, n);,歸并排序,關(guān)鍵問(wèn)題:怎樣完成一趟歸并?,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄,歸并的步長(zhǎng)是2h,在歸并過(guò)程中,有以下三種情況:,若in-h+1,則表明只剩下一個(gè)有序表,直接將該有序表送到r1的相應(yīng)位置,完成后退出一趟歸并。,i=9 n-h+1=8,歸并排序,關(guān)鍵問(wèn)題:怎樣完成一趟歸并?,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄,歸并的步長(zhǎng)是2h,在歸并過(guò)程中,有以下三種情況:,若in-h+

溫馨提示

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

最新文檔

評(píng)論

0/150

提交評(píng)論