數(shù)據(jù)結(jié)構(gòu)課件第十章

第1頁，共47頁，2023年，2月20日，星期六排序:設(shè)n

個記錄的序列為{R1,R2,R3,...,Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,K3,...,Kn}若規(guī)定1,2,3,...,n的一個排列p1,p2,p3,...,pn

，使得相應(yīng)的關(guān)鍵字滿足如下非遞減關(guān)系:Kp≤Kp≤Kp≤...≤Kp123n則原序列變?yōu)橐粋€按關(guān)鍵字有序的序列:Rp,Rp,Rp,...,Rp123n{}此操作過程稱為排序。第2頁，共47頁，2023年，2月20日，星期六穩(wěn)定排序與不穩(wěn)定排序假設(shè)Ki=Kj

，且排序前序列中Ri

領(lǐng)先于Rj

；若在排序后的序列中Ri

仍領(lǐng)先于Rj

，則稱排序方法是穩(wěn)定的。若在排序后的序列中Rj

仍領(lǐng)先于Ri

，則稱排序方法是不穩(wěn)定的。例，序列3158

869若排序后得368

8915穩(wěn)定的若排序后得368

8915不穩(wěn)定的第3頁，共47頁，2023年，2月20日，星期六內(nèi)部排序與外部排序內(nèi)部排序:

指的是待排序記錄存放在計算機隨機存儲器中進(jìn)行的排序過程。外部排序:

指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。第4頁，共47頁，2023年，2月20日，星期六內(nèi)部排序按照排序過程中所依據(jù)的原則的不同可以分類為:插入排序交換排序(快速排序)選擇排序歸并排序基數(shù)排序二叉排序樹排序第5頁，共47頁，2023年，2月20日，星期六10.2插入排序10.2.1直接插入排序思想:利用有序表的插入操作進(jìn)行排序有序表的插入:

將一個記錄插入到已排好序的有序表中，從而得到一個新的有序表。例，序列132738657697插入4913273849

657697第6頁，共47頁，2023年，2月20日，星期六例，序列49386597761327初始，S={49}；{3849}算法描述:初始，令第1

個元素作為初始有序表；依次插入第

2,3,…,k

個元素構(gòu)造新的有序表；直至最后一個元素；{384965}{38496597}{3849657697}{133849657697}{13273849657697}直接插入排序算法主要應(yīng)用比較和移動兩種操作。第7頁，共47頁，2023年，2月20日，星期六10.2.2希爾(shell)排序分析直接插入排序1.若待排序記錄序列按關(guān)鍵字基本有序，則排序效率可大大提高；2.待排序記錄總數(shù)越少，排序效率越高；第8頁，共47頁，2023年，2月20日，星期六思想:先將待排序記錄序列分割成為若干子序列分別進(jìn)行直接插入排序；待整個序列中的記錄基本有序后，再全體進(jìn)行一次直接插入排序。例，序列493865977613274855419第一趟排序491319382765489755764131949273848655597476第9頁，共47頁，2023年，2月20日，星期六第二趟排序13194927384865559747613553876274

654948199713385576427

4965194897第三趟排序4131927

38

4849

556576

97第10頁，共47頁，2023年，2月20日，星期六10.3交換排序10.3.1冒泡排序思想:

通過不斷比較相鄰元素大小，進(jìn)行交換來實現(xiàn)排序。首先將第一個元素與第二個元素比較大小，若為逆序，則交換；然后比較第二個元素與第三個元素的大小，若為逆序，則交換；...直至比較第n-1個元素與第n個元素的大小，若為逆序，則交換；第一趟排序:結(jié)果:關(guān)鍵字最大的記錄被交換至最后一個元素位置上。第11頁，共47頁，2023年，2月20日，星期六例，序列4938761327493876132738

49

13

27384913762776初始第一趟排序后最大值13

492749次大值第二趟排序后3813

27132713382738第三趟排序后第四趟排序后第12頁，共47頁，2023年，2月20日，星期六10.3.2快速排序冒泡排序的一種改進(jìn)算法。思想:以首記錄作為軸記錄，從前、后雙向掃描序列，通過交換，實現(xiàn)大值記錄后移，小值記錄前移，最終將軸記錄安置在一個適當(dāng)?shù)奈恢谩?小值記錄在前、大值記錄在后)軸記錄將原序列分割成兩部分，依次對前后兩部分重新設(shè)定軸記錄，繼而分別再進(jìn)行快速排序。直至整個序列有序。第13頁，共47頁，2023年，2月20日，星期六例，序列{4938659776132752}第一趟排序4938659776132752ij從前尋找大于軸記錄的記錄，從后尋找小于軸記錄的記錄；ij交換大值記錄與小值記錄；2765重復(fù)上述兩步操作，直至i＞j

；ji1397ji交換軸記錄和標(biāo)識j

指示的記錄。13

49第14頁，共47頁，2023年，2月20日，星期六第一趟排序后133827

49

76976552第二趟排序1338277697655249將序列分成兩部分，分別進(jìn)行新的快速排序；第二趟排序后13382765

527697第三趟排序38276552第三趟排序后27385265最終有序序列為:13273852657697第15頁，共47頁，2023年，2月20日，星期六10.4選擇排序思想:

每一趟都選出一個最大或最小的元素，并放在合適的位置。簡單選擇排序樹形選擇排序堆排序第16頁，共47頁，2023年，2月20日，星期六10.4.1簡單選擇排序思想:第1趟選擇:從1—n

個記錄中選擇關(guān)鍵字最小的記錄，并和第1個記錄交換。第2趟選擇:從2—n

個記錄中選擇關(guān)鍵字最小的記錄，并和第2

個記錄交換。第n-1趟選擇:從n-1—n

個記錄中選擇關(guān)鍵字最小的記錄，并和第n-1

個記錄交換。...第17頁，共47頁，2023年，2月20日，星期六例，序列4938976576第1趟選擇:min3849976576第2趟選擇:min38

49976576第3趟選擇:min38

49

659776第4趟選擇:min38

49

65

7697第18頁，共47頁，2023年，2月20日，星期六選擇排序的主要操作是進(jìn)行關(guān)鍵字間的比較。在n個關(guān)鍵字中選出最小值，至少需要n-1次比較。在剩余的n-1個關(guān)鍵字中選出最小值，至少需要n-2次比較？如果能利用前n-1次比較所得信息，可以減少后面選擇的比較次數(shù)。體育比賽中的錦標(biāo)賽:第19頁，共47頁，2023年，2月20日，星期六10.4.3堆排序堆:

一棵完全二叉樹，任一個非終端結(jié)點的值均小于等于(或大于等于)其左、右兒子結(jié)點的值。例，1285473053362491963811

98324根結(jié)點為最小值根結(jié)點為最大值第20頁，共47頁，2023年，2月20日，星期六2.把這棵普通的完全二叉樹改造成堆，便可獲取最小值；思想:3.輸出最小值；4.刪除根結(jié)點，繼續(xù)改造剩余樹成堆，便可獲取次小值；5.輸出次小值；6.重復(fù)改造，輸出次次小值、次次次小值，直至所有結(jié)點均輸出，便得到一個排序。1.將序列構(gòu)造成一棵完全二叉樹；第21頁，共47頁，2023年，2月20日，星期六最大堆的初始化根據(jù)inta[10]={20,12,35,15,10,80,30,17,2,1}建立最大堆20123515108030172112345678910算法：從第一個具有孩子的結(jié)點i開始（i=[n/2]），如果以這個元素為根的子樹已是最大堆，則不需調(diào)整，否則需調(diào)整子樹使之成為堆。繼續(xù)檢查i-1，i-2等結(jié)點為根的子樹，直到檢查整個二叉樹的根結(jié)點(其位置為１)。第22頁，共47頁，2023年，2月20日，星期六最大堆的初始化step1已知n=10;i=n/2=5;20123515108030172112345678910i2012351510803017210123456789第23頁，共47頁，2023年，2月20日，星期六最大堆的初始化step2i=4201235151080301721123456789102012351510803017210123456789i2i2i+1第24頁，共47頁，2023年，2月20日，星期六最大堆的初始化step3i=3201235171080301521123456789102012351710803015210123456789i2i2i+1第25頁，共47頁，2023年，2月20日，星期六最大堆的初始化step4_0i=2201280171035301521123456789102012801710353015210123456789i2i2i+1第26頁，共47頁，2023年，2月20日，星期六最大堆的初始化step4_1i=2,j=2i=4201780121035301521123456789102017801210353015210123456789j2j2j+1第27頁，共47頁，2023年，2月20日，星期六最大堆的初始化step5_0i=5201780151035301221123456789102017801510353012210123456789i2i2i+1第28頁，共47頁，2023年，2月20日，星期六最大堆的初始化step5_1i=1,j=2i+1=3801720151035301221123456789108017201510353012210123456789j2j2j+1第29頁，共47頁，2023年，2月20日，星期六最大堆的初始化step5_2801735151020301221123456789108017351510203012210123456789第30頁，共47頁，2023年，2月20日，星期六例，序列49386597761327501.按順序依次構(gòu)造成完全二叉樹的結(jié)點；49386597761327502.把完全二叉樹改造成堆；從下向上，父子交換；50971365134949273.取得最小值134.刪除13

，重新改造成新堆；1397279797495.取得次小值27；6.刪除27

，重新改造成新堆；9727973897507.取得次次小值38；第31頁，共47頁，2023年，2月20日，星期六10.5歸并排序歸并:

將兩個或兩個以上的有序表合并成一個新的有序表。有序線性表、有序鏈表的歸并；利用歸并的思想實現(xiàn)排序:初始，n個記錄看作是n

個有序的子序列，長度為

1

；兩兩歸并，得到n/2

個長度為2或1

的有序的子序列；再兩兩歸并；重復(fù)執(zhí)行直至得到一個長度為n

的有序序列為止。這種排序方法稱為2—路歸并排序。第32頁，共47頁，2023年，2月20日，星期六例，序列{49,38,65,97,76,13,27}初始[49]

[38][65][97][76][13][27]一趟歸并[3849][6597][1376][27]二趟歸并[38496597][132776]三趟歸并[13273849657697]第33頁，共47頁，2023年，2月20日，星期六10.6基數(shù)排序是一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進(jìn)行排序的方法。10.6.1多關(guān)鍵字排序撲克牌問題:已知撲克牌中52張牌面的次序關(guān)系定義為:?

＜

?

＜

?

＜

?花色:面值:2＜3＜＜A...例，?8

?

3＜花色優(yōu)先級更高，為主關(guān)鍵字，面值為次關(guān)鍵字第34頁，共47頁，2023年，2月20日，星期六52張牌排序方法:最高位優(yōu)先法(MSDF):先按不同“花色”分成有次序的4堆，每一堆均具有相同的花色；然后分別對每一堆按“面值”大小整理有序。最低位優(yōu)先法(LSDF):先按不同“面值”分成13堆；然后將這13堆牌自小至大疊在一起(2,3,...,A)；然后將這付牌整個顛倒過來再重新按不同的“花色”分成4堆；最后將這4堆牌按自小至大的次序合在一起。收集分配第35頁，共47頁，2023年，2月20日，星期六10.6.2基數(shù)排序基數(shù)排序就是借助于“分配”和“收集”兩種操作實現(xiàn)對單邏輯關(guān)鍵字的排序。首先，單邏輯關(guān)鍵字通常都可以看作是由若干關(guān)鍵字復(fù)合而成。其次，利用LSDF法實現(xiàn)對若干關(guān)鍵字的排序。例，若關(guān)鍵字是數(shù)值，且值域為0≤K≤999，故可以將K

看作是由3個關(guān)鍵字K0K1K2

組成，例，603是由603

組成。第36頁，共47頁，2023年，2月20日，星期六例，序列278109063930589184505269008083第一趟分配0123456789278109063930589184505269008083第一趟收集930063083184505278008109589269第二趟分配0123456789930063083184505278008109589269第二趟收集505008109930063269278083184589第37頁，共47頁，2023年，2月20日，星期六第二趟收集505008109930063269278083184589第三趟分配0123456789505008109930063269278083184589第三趟收集008063083109184269278505589930第38頁，共47頁，2023年，2月20日，星期六一個對象序列的排序碼為{46，79，56，38，40，84}，采用快速排序以位于最左位置的對象為基準(zhǔn)而得到的第一次劃分結(jié)果為（）。

A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}

第39頁，共47頁，2023年，2月20日，星期六設(shè)有5000個無序的元素，希望用最快的速度挑選出其中前50個最大的元素，最好選用(

)法。

A．冒泡排序