數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第1頁!9.1概述9.2插入排序9.3交換排序9.4選擇排序9.5歸并排序9.6基數(shù)排序第十章內(nèi)部排序2數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第2頁!10.1概述1、排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“按關(guān)鍵字有序”的記錄序列。52，49，80，36，14，58，61，23，97，7514，23，36，49，52，58，61，75，80，97一般情況下，假設(shè)含n個記錄的序列為{R1，R2，……，Rn}其相應(yīng)的關(guān)鍵字序列為{K1，K2，……，Kn}這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在這樣一個關(guān)系：Kp1<=Kp2<=…<=Kpn按此固有關(guān)系將上式記錄序列重新排列為{Rp1,Rp2,…,Rpn}的操作稱作排序3數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第3頁!2、關(guān)鍵字數(shù)據(jù)對象有多個屬性域，即多個數(shù)據(jù)成員組成，其中有一個屬性域可以用來區(qū)分對象，作為排序依據(jù)，稱為關(guān)鍵字。關(guān)鍵字與記錄之間是一對一的關(guān)系稱主關(guān)鍵字關(guān)鍵字與記錄之間是一對多的關(guān)系稱次關(guān)鍵字4數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第4頁!5、什么叫內(nèi)部排序？什么叫外部排序——若待排序記錄都在內(nèi)存中，稱內(nèi)部排序——若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。注：外部排序時，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時放入內(nèi)存，顯然外部排序要復(fù)雜得的多。內(nèi)部排序和外部排序的不同在于能否一次處理完所有數(shù)據(jù)5數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第5頁!7.內(nèi)部排序的算法有哪些？——按排序的規(guī)則不同，可分為5類：插入排序交換排序（重點是快速排序）選擇排序歸并排序基數(shù)排序d＝關(guān)鍵字的位數(shù)(長度)——按排序算法的時間復(fù)雜度不同，可分為3類：簡單的排序算法：時間效率低，O(n2)先進的排序算法:時間效率高，O(nlog2n)基數(shù)排序算算法：時間效率高，O(d×n)6數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第6頁!1)直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請寫出直接插入排序的中間過程序列。【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】

在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。最簡單的排序法！7數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第7頁!2）折半插入排序優(yōu)點：比較的次數(shù)大大減少，全部元素比較次數(shù)僅為O(nlog2n)。時間效率：雖然比較次數(shù)大大減少，可惜移動次數(shù)并未減少，所以排序效率仍為O(n2)?？臻g效率：

O（1）穩(wěn)定性：穩(wěn)定對應(yīng)程序見教材P267（僅用于順序表）新元素插入到哪里？討論：若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？答：直接插入不僅可行，而且還無需移動元素，時間效率更高！在已形成的有序表中折半查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。但鏈表無法“折半”！8數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第8頁!例：有6個記錄，前5個已排序的基礎(chǔ)上，對第6個記錄排序。[1527365369]42

lowmidhigh

[1527365369]42

lowhigh

mid

[1527365369]42

[152736425369](42>36)(42<53)9數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第9頁!例對下列序列采用希爾排序49386597761327495504趟希爾排序增量為5493865977613274955041349273849659755047610數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第10頁!例對下列序列采用希爾排序49386597761327495504第三趟希爾排序增量為1133855042765494997760413273849495565769711數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第11頁!9.3交換排序兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。交換排序的主要算法有：1)冒泡排序2)快速排序交換排序的基本思想是：12數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第12頁!2）快速排序從待排序列中任取一個元素(例如取個)作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個子表的元素只剩一個。此時便為有序序列了?；舅枷耄簝?yōu)點：因為每趟可以確定不止一個元素的位置，而且呈指數(shù)增加，所以特別快！前提：順序存儲結(jié)構(gòu)

13數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第13頁!例對下列序列采用快速排序4938659776132749第趟快速排序14938659776132749樞軸lowhigh49lowhighlowhighhighlow==high則此位置就是樞軸49的最終位置趟快速排序結(jié)束14數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第14頁!例對下列序列采用快速排序4938659776132749第趟快速排序2然后對49之后的數(shù)據(jù)采用快速排序13384976976549樞軸76lowhighlowLow==high76樞軸76后面的97也不需再次排序2797第二趟快速排序結(jié)束15數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第15頁!關(guān)鍵字序列T=（21，25，49，25*，16，08），請給出快速排序的具體實現(xiàn)過程。16數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第16頁!時間效率快速排序在平均情況下的時間復(fù)雜性為O(nlog2n)，通常認為是在所有同數(shù)量級排序算法中，平均情況下最佳的排序方法。但是，在最壞的情況下(待排記錄有序)的快速排序會蛻變成為冒泡排序，時間復(fù)雜度為O(n2)。可以采用一些改進措施盡量避免這種情況的出現(xiàn)?？臻g效率快速排序是遞歸算法，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)，遞歸的次數(shù)決定額外空間的多少。最理想的遞歸次數(shù)是log2(n+1)，故空間復(fù)雜度為O(log2n)。穩(wěn)定性快速排序為不穩(wěn)定的排序算法。

12345678910效率分析

17數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第17頁!1）簡單選擇排序思路簡單：每經(jīng)過一趟比較就找出一個最小值，與待排序列最前面的位置互換即可?！紫?，在n個記錄中選擇最小者放到r[1]位置；然后，從剩余的n-1個記錄中選擇最小者放到r[2]位置；…如此進行下去，直到全部有序為止。優(yōu)點：實現(xiàn)簡單缺點：每趟只能確定一個元素，表長為n時需要n-1趟前提：順序存儲結(jié)構(gòu)

18數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第18頁!2）堆排序1.什么是堆？堆的定義：設(shè)有n個元素的序列k1，k2，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時，稱之為堆。ki≤

k2iki≤

k2i+1ki≥

k2iki≥

k2i+1或者i=1,2,…n/22.怎樣建堆？3.怎樣堆排序？解釋：如果讓滿足以上條件的元素序列（k1，k2，…，kn）順次排成一棵完全二叉樹，則此樹的特點是：樹中所有結(jié)點的值均大于（或小于）其左右孩子，此樹的根結(jié)點（即堆頂）必最大（或最小）。19數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第19頁!082546495867234561（大根堆）918566765867234561557例：有序列T1=（08,25,49,46,58,67）和序列T2=（91,85,76,66,58,67,55）,判斷它們是否“堆”？√（小根堆）√（小頂堆）（最小堆）（大頂堆）（最大堆）20數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第20頁!關(guān)鍵：將堆的當(dāng)前頂點輸出后，如何將剩余序列重新調(diào)整為堆？方法：將當(dāng)前頂點與堆尾記錄交換，然后仿建堆動作重新調(diào)整，如此反復(fù)直至排序結(jié)束。3.怎樣進行堆排序？21數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第21頁!1625*21082549交換1號與5號記錄08

252125*1649從1號到5號重新調(diào)整為最大堆082525*2116491234561625*08252149136542082525*2508

2125*1649082525*21

08164922數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第22頁!08162125*2549交換1號與3號記錄21160825*2549從1號到3號重新調(diào)整為最大堆211625*082549123456081625*25214913654223數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第23頁!9.5歸并排序歸并排序的基本思想是：將兩個（或以上）的有序表組成新的有序表。更實際的意義：可以把一個長度為n的無序序列看成是n個長度為1的有序子序列，首先做兩兩歸并，得到n/2個長度為2的子序列；再做兩兩歸并，…，如此重復(fù)，直到最后得到一個長度為n的有序序列。例：關(guān)鍵字序列T=（21，25，49，25*，93，62，72，08，37，16，54），請給出歸并排序的具體實現(xiàn)過程。24數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第24頁!歸并排序算法分析：

時間效率：

O(nlog2n)因為在遞歸的歸并排序算法中，函數(shù)Merge()做一趟兩路歸并排序，需要調(diào)用merge()函數(shù)n/(2*len)

O(n/len)次，函數(shù)Merge()調(diào)用Merge()正好log2n次，而每次merge()要執(zhí)行比較O(len)次，所以算法總的時間復(fù)雜度為O(nlog2n)?？臻g效率：

O(n)因為需要一個與原始序列同樣大小的輔助序列（TR）。這正是此算法的缺點。穩(wěn)定性：穩(wěn)定25數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第25頁!1.什么是“多關(guān)鍵字”排序？實現(xiàn)方法？例1：對一副撲克牌該如何排序？若規(guī)定花色和面值的順序關(guān)系為：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A則可以先按花色排序，花色相同者再按面值排序；也可以先按面值排序，面值相同者再按花色排序。例2：職工分房該如何排序？河大規(guī)定：先以總分排序（職稱分＋工齡分）；總分相同者，再按配偶總分排序，其次按配偶職稱、工齡、人口……等等排序。以上兩例都是典型的多關(guān)鍵字排序！26數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第26頁!2.單邏輯關(guān)鍵字怎樣“按位值”排序？設(shè)n個記錄的序列為：{V0,V1,…,Vn-1}，可以把每個記錄Vi的單關(guān)鍵碼Ki看成是一個d元組（Ki1,Ki2,…,Kid），則其中的每一個分量Kij(1jd)也可看成是一個關(guān)鍵字。4注1：

Ki1＝最高位，Kid＝最低位；Ki共有d位，可看成d元組；注2：每個分量Kij

(1

j

d)有radix種取值，則稱radix為基數(shù)。26(9,8,4)(0,1,…,9)（a,b,…,z）(d,i,a,n)310例1：關(guān)鍵碼984可以看成是

元組；基數(shù)radix為

。例2：關(guān)鍵碼dian可以看成是

元組；基數(shù)radix為

。思路：27數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第27頁!例：T=（02，77，70，54，64，21，55，11），用LSD排序。分析：①各關(guān)鍵字可視為2元組；②每位的取值范圍是：0-9；即基數(shù)radix＝10。因此，特設(shè)置10個隊列，并編號為0-9。1155216454707702原始序列12345678先對低位掃描出隊012345678910個隊列計算機怎樣實現(xiàn)LSD算法？分配過程收集過程下一步775564540211217012345678出隊后序列775554，6421，117002又稱散列過程！28數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第28頁!請實現(xiàn)以下關(guān)鍵字序列的鏈?zhǔn)交鶖?shù)排序：T=（614，738，921，485，637，101，215，530，790，306）例:614921485637738101215530790306趟分配e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]614738921485637101215530790306f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]原始序列鏈表：r[0]→（從最低位i=3開始排序，f[]

是隊首指針，e[]

為隊尾指針）趟收集（讓隊尾指針e[i]

鏈接到下一非空隊首指針f[i+1]

即可）530790921101614485215306637738r[0]→29數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第29頁!第二趟收集的結(jié)果：530790921101614485215306637738e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]614738921485637101215530790306f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]第三趟分配（按最高位i=1）第三趟收集（讓隊尾指針e[i]

鏈接到下一非空隊首指針f[i+1]

）530790921101614485215306637738r[0]→r[0]→排序結(jié)束！30數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第30頁!各種內(nèi)部排序方法的比較

(教材P289）排序方法最好情況平均時間最壞情況輔助存儲穩(wěn)定性簡單排序O(n)O(n2)O(n2)O(1）穩(wěn)定快速排序O(nlgn)O(nlgn)O(n2)O(lgn)不穩(wěn)定堆排序O(nlgn)O(nlgn)O(nlgn)O(1）不穩(wěn)定歸并排序O(nlgn)O(nlgn)O(nlgn)O(n）穩(wěn)定基數(shù)排序O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd)穩(wěn)定簡單選擇O(n2)O(n2)O(n2)O(1）不穩(wěn)定直接插入O(n)O(n2)O(n2)O(1）穩(wěn)定折半插入O(nlgn)O(nlgn)O(nlgn)O(1）穩(wěn)定冒泡O(n)O(n2)O(n2)O(1）穩(wěn)定31數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第31頁!3、排序的目的是什么？——便于查找4、排序算法的好壞如何衡量？時間效率——排序速度（即排序所花費的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性——若兩個記錄A和B的關(guān)鍵字相等，但排序后A，B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。32數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第32頁!6、排序主要做的工作：比較+移動33數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第33頁!9.2插入排序插入排序的基本思想是：插入排序有多種具體實現(xiàn)算法：1)直接插入排序2)折半插入排序3)希爾排序每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。34數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第34頁!例題對下列存放在數(shù)組A中的序列采用直接插入排序法排序。4938659713762749A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]監(jiān)視哨注

紫色表示待排數(shù)據(jù)；藍色表示已經(jīng)有序數(shù)據(jù)4938第

趟插入排序1待排元素38493838652待排元素4965973待排元素97764待排元素7697765待排元素971376136549381397276待排元素762765493827待排元素797497665494949排序趟數(shù)=數(shù)據(jù)個數(shù)-135數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第35頁!例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請寫出直接插入排序的中間過程序列?！?3】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】

36數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第36頁!3）希爾（shell）排序（又稱縮小增量排序）基本思想：先將整個待排記錄序列分割成若干子序列,分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。技巧：子序列的構(gòu)成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。優(yōu)點：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。37數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第37頁!例對下列序列采用希爾排序49386597761327495504第二趟希爾排序增量為3134927384965975504761338557604276549499738數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第38頁!時間性能：希爾排序的分析非常困難，原因是何種步長序列最優(yōu)難以斷定。通常認為時間復(fù)雜度為：O(n3/2)。較好的步長序列：……121、40、13、4、1;可由遞推公式Si=3Si-1+1產(chǎn)生。空間性能：只用一個額外空間，空間復(fù)雜度為O(1)；穩(wěn)定性：希爾排序是不穩(wěn)定的排序算法效率分析

39數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第39頁!1)冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點：每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。前提：順序存儲結(jié)構(gòu)

例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出冒泡排序的具體實現(xiàn)過程。21，25，49，25*，16，0821，25，25*，16，08，4921，25，16，08，25*，4921，16，08，25，

25*，4916，08，21，

25，

25*，4908，16，

21，

25，

25*，49初態(tài)：第1趟第2趟第3趟第4趟第5趟40數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第40頁!快速排序舉例初始關(guān)鍵字：{49，38，65，97，76，13，27，49}pivotkey49jji1次交換后：{27，38，65，97，76，13，，49}iji2次交換后：{27，38，，97，76，13，65，49}ijj3次交換后：{27，38，13，97，76，，65，49}iji4次交換后：{27，38，13，，76，97，65，49}jij一趟完成后：{27，38，13，49，76，97，65，49}41數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第41頁!例對下列序列采用快速排序4938659776132749第趟快速排序122738134976976549樞軸首先對49之前的數(shù)據(jù)采用快速排序27lowhighlow==high27樞軸27之前和之后都只有一個值，不再需要排序133842數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第42頁!例對下列序列采用快速排序4938659776132749第趟快速排序231338494965762797樞軸對76之前的數(shù)據(jù)采用快速排序49highlowlow==high4965整個排序結(jié)束43數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第43頁!“快速排序”是否真的比任何排序算法都快？設(shè)每個子表的支點都在中間（比較均衡），則：第1趟比較，可以確定1個元素的位置；第2趟比較（2個子表），可以再確定2個元素的位置；第3趟比較（4個子表），可以再確定4個元素的位置；第4趟比較（8個子表），可以再確定8個元素的位置；……只需log2n＋1趟便可排好序。——基本上是！因為每趟可以確定的數(shù)據(jù)元素是呈指數(shù)增加的！而且，每趟需要比較和移動的元素也呈指數(shù)下降，加上編程時使用了交替逼近技巧，更進一步減少了移動次數(shù)，所以速度特別快。1234567891044數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第44頁!9.4選擇排序選擇排序有多種具體實現(xiàn)算法：1)簡單選擇排序2)堆排序選擇排序的基本思想是：每一趟在后面n-i

個待排記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個記錄。45數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第45頁!例：關(guān)鍵字序列T=（21，25，49，25*，16，08），請給出簡單選擇排序的具體實現(xiàn)過程。原始序列：

21，25，49，25*，16，08直接選擇排序第1趟第2趟第3趟第4趟第5趟08，25，49，25*，16，2108，16,49，25*，25，2108，16,

21，25*，25，4908，16,

21，25*，25，4908，16,

21，25*，25，49時間效率：O(n2)——雖移動次數(shù)較少，但比較次數(shù)仍多?？臻g效率：O（1）——無需任何附加單元！算法的穩(wěn)定性：不穩(wěn)定——因為排序時，25*到了25的前面。最小值08與r[1]交換位置46數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第46頁!123456789注意：對于結(jié)點i，i>n/2時，表示結(jié)點i為葉子結(jié)點。47數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第47頁!步驟：從最后一個非終端結(jié)點開始往前逐步調(diào)整，讓每個雙親大于（或小于）子女，直到根結(jié)點為止。212525*491608123456例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請建大根堆。2.怎樣建堆？解：為便于理解，先將原始序列畫成完全二叉樹的形式：完全二叉樹的個非終端結(jié)點編號必為n/2

??！(性質(zhì)5)注：終端結(jié)點（即葉子）沒有任何子女，無需單獨調(diào)整。21i=3:49大于08，不必調(diào)整；i=2:25大于25*和16，也不必調(diào)整；i=1:21小于25和49，要調(diào)整！49而且21還應(yīng)當(dāng)向下比較?。?8數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第48頁!08252125*1649交換1號與6號記錄492525*21160812345649252125*1608初始最大堆2525*16211365420849例：對剛才建好的大根堆進行排序：49數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第49頁!08162125*2549交換1號與4號記錄25*1621082549從1號到4號重新調(diào)整為最大堆25*1608212549123456081625*25214913654250數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第50頁!08162125*2549交換1號與2號記錄160821

25*2549從1號到2號重新調(diào)整為最大堆160825*212549123456081625*25214913654251數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第51頁!212525*9362720837165449212525*4962930872163754163754212525*490862729308212525*496272930816212525*374954627293len=1len=2len=4len=8len=16163754整個歸并排序僅需log2n趟52數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第52頁!9.6基數(shù)排序(RadixSort)要討論的問題：1.什么是“多關(guān)鍵字”排序？實現(xiàn)方法？2.單邏輯關(guān)鍵字怎樣“按位值”排序？基數(shù)排序的基本思想是：借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進行排序。即：用關(guān)鍵字不同的位值進行排序。53數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第53頁!多關(guān)鍵字排序的實現(xiàn)方法通常有兩種：最高位優(yōu)先法MSD(MostSignificantDigitfirst)例：對一副撲克牌該如何排序？答：若規(guī)定花色為關(guān)鍵字（高位），面值為第二關(guān)鍵字（低位），則使用MSD和LSD方法都可以達到排序目的。MSD方法的思路：先設(shè)立4個花色“箱”，將全部牌按花色分別歸入4個箱內(nèi)（每個箱中有13張牌）；然后對每個箱中的牌按面值進行插入排序（或其它穩(wěn)定算法）。LSD方法的思路：先按面值分成13堆（每堆4張牌），然后對每堆中的牌按花色進行排序（用插入排序等穩(wěn)定的算法）。想一想：用哪種方法更快些？最低位優(yōu)先法LSD(LeastSignificantDigitfirst)54數(shù)據(jù)結(jié)構(gòu)課件第十章共59頁，您現(xiàn)在瀏覽的是第54頁!因為有分組，故此算法需遞歸實現(xiàn)。討論：是借用MSD方式來排序呢，還是借用LSD方式？例：初始關(guān)鍵字序列T=（32,13,27,32*,19，33），請分別用MSD和LSD進行排序，并討論其優(yōu)缺點。法1（MSD）：原始序列：32,13,27,32*,