數(shù)據(jù)結(jié)構(gòu)：第10章排序A

1、1 10.1 10.6 10.8 10.25 10.4210.1 10.6 10.8 10.25 10.4212周四周四截止截止2基本要求：基本要求：自編堆排序或錦標賽排序自編堆排序或錦標賽排序+折半查找算法折半查找算法高級要求：高級要求：自行設(shè)計一個方案來體現(xiàn)排序及查找功自行設(shè)計一個方案來體現(xiàn)排序及查找功能。能。寫成寫成“實驗指導書實驗指導書”的形式網(wǎng)上或郵件提交的形式網(wǎng)上或郵件提交例如：日程安排管理程序例如：日程安排管理程序 歌詞搜索歌詞搜索 個人理財管理個人理財管理或：種子杯復賽或決賽題或：種子杯復賽或決賽題3410.1 10.1 概述概述10.2 10.2 插入排序插入排序10.3 1

2、0.3 交換排序交換排序10.4 10.4 選擇排序選擇排序10.5 10.5 歸并排序歸并排序10.6 10.6 基數(shù)排序基數(shù)排序510.1 10.1 概述概述1. 什么是排序？什么是排序？ 將一組雜亂無章的將一組雜亂無章的數(shù)據(jù)數(shù)據(jù)按一定的按一定的規(guī)律規(guī)律順次排列起來。順次排列起來。2. 排序的目的是什么？排序的目的是什么？存放在數(shù)據(jù)表中存放在數(shù)據(jù)表中按關(guān)鍵字排序按關(guān)鍵字排序3.3.排序算法的好壞如何衡量？排序算法的好壞如何衡量？ 時間效率時間效率排序速度（即排序所花費的全部比較次數(shù)）排序速度（即排序所花費的全部比較次數(shù)） 空間效率空間效率占內(nèi)存輔助空間的大小占內(nèi)存輔助空間的大小 穩(wěn)定性穩(wěn)定

3、性若兩個記錄若兩個記錄A A和和B B的關(guān)鍵字值相等，但排序后的關(guān)鍵字值相等，但排序后A A、B B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。 便于查找！便于查找！64. 什么叫內(nèi)部排序？什么叫外部排序什么叫內(nèi)部排序？什么叫外部排序？ 若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；若待排序記錄一部分在內(nèi)存，一部分在外存，則若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。稱為外部排序。注：注：外部排序時，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間外部排序時，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時放入外存，顯然外部

4、排序要復雜得多。結(jié)果還要及時放入外存，顯然外部排序要復雜得多。 5.5.待排序記錄在內(nèi)存中怎樣存儲和處理？待排序記錄在內(nèi)存中怎樣存儲和處理？ 順序順序排序排序排序時直接移動記錄；排序時直接移動記錄； 鏈表鏈表排序排序排序時只移動指針；排序時只移動指針； 地址地址排序排序排序時先移動地址，最后再移動記錄。排序時先移動地址，最后再移動記錄。注：注：地址排序地址排序中可以增設(shè)一維數(shù)組來專門存放記錄的地址。中可以增設(shè)一維數(shù)組來專門存放記錄的地址。7注：注：大多數(shù)排序算法都是針對大多數(shù)排序算法都是針對順序表順序表結(jié)構(gòu)的結(jié)構(gòu)的( (便于直接移動元素便于直接移動元素) )6. 6. 順序存儲（順序表）的抽象

5、數(shù)據(jù)類型如何表示？順序存儲（順序表）的抽象數(shù)據(jù)類型如何表示？Typedef struct /定義每個記錄定義每個記錄（數(shù)據(jù)元素）的結(jié)構(gòu)（數(shù)據(jù)元素）的結(jié)構(gòu) KeyType key ; /關(guān)鍵字關(guān)鍵字 InfoType otherinfo; /其它數(shù)據(jù)項其它數(shù)據(jù)項RecordType，node ; /例如例如node.keynode.key表示其中一個分量表示其中一個分量Typedef struct /定義順序表定義順序表L L的結(jié)構(gòu)的結(jié)構(gòu) RecordType r MAXSIZE +1 ; /存儲順序表的向量存儲順序表的向量 /r0/r0一般作哨兵或緩沖區(qū)一般作哨兵或緩沖區(qū) int length

6、 ; /順序表的長度順序表的長度SqList ,L; /例如例如L.rL.r或或L.lengthL.length表示其中一個分量表示其中一個分量# define MAXSIZE 20 /設(shè)記錄數(shù)不超過設(shè)記錄數(shù)不超過2020個個（本章都如此假設(shè)（本章都如此假設(shè)）typedef int KeyType ; /設(shè)關(guān)鍵字為整型量（設(shè)關(guān)鍵字為整型量（intint型）型）若若r r數(shù)組是表數(shù)組是表L L中的一個分量且為中的一個分量且為nodenode類型，類型，則則r r中某元素的中某元素的keykey分量表示為：分量表示為：ri.keyri.key87. 內(nèi)部排序的算法有哪些？內(nèi)部排序的算法有哪些？按排

7、序的規(guī)則不同，可分為按排序的規(guī)則不同，可分為5類：類：v插入排序插入排序v交換排序交換排序（重點是快速排序）（重點是快速排序）v選擇排序選擇排序v歸并排序歸并排序v基數(shù)排序基數(shù)排序d關(guān)鍵字的位數(shù)關(guān)鍵字的位數(shù)(長度長度)按排序算法的時間復雜度不同，可分為按排序算法的時間復雜度不同，可分為3類：類：v簡單的排序算法：時間效率低，簡單的排序算法：時間效率低，O(n2)v先進的排序算法先進的排序算法: 時間效率高，時間效率高，O( nlog2n )v基基 數(shù)數(shù) 排排 序序 算法：時間效率高，算法：時間效率高，O( dn)910.2 10.2 插入排序插入排序插入排序有多種具體實現(xiàn)算法：插入排序有多種具

8、體實現(xiàn)算法： 1) 直接插入排序直接插入排序 2) 折半插入排序折半插入排序 3）2-路插入排序路插入排序 4) 表插入排序表插入排序 5) 希爾排序希爾排序小改進小改進大改進大改進10新元素插入到哪里？新元素插入到哪里？例例1 1：關(guān)鍵字序列關(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

9、【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】 在已形成的在已形成的有序表中有序表中線性查找線性查找，并在，并在適當位置插入，把原來位置上的元素向后適當位置插入，把原來位置上的元素向后順移順移。最簡單的排序法！最簡單的排序法！11例例1 1：關(guān)鍵字序列關(guān)鍵字序列T= （21，25，49，25*，16，08），），請寫出直接插入排序的具體實現(xiàn)過程。請寫出直接插入排序的具體實現(xiàn)過程。* *表示后一個表示后一個25250 1 2 3

10、4 5 6252525* * *161616080808解：解：假設(shè)該序列已存入一維數(shù)組假設(shè)該序列已存入一維數(shù)組r7r7中，將中，將r0r0作為哨兵作為哨兵（TempTemp）。則程序執(zhí)行過程為：）。則程序執(zhí)行過程為：初態(tài)：初態(tài)：時間效率：時間效率： 因為在最壞情況下，所有元素的比較次數(shù)總和為因為在最壞情況下，所有元素的比較次數(shù)總和為（0 01 1n-1)O(nn-1)O(n2 2) )。其他情況下也要考慮。其他情況下也要考慮移動元素的次數(shù)。移動元素的次數(shù)。 故時間復雜度為故時間復雜度為O(nO(n2 2) ) 空間效率：空間效率：僅占用僅占用1 1個緩沖單元個緩沖單元算法的穩(wěn)定性：算法的穩(wěn)定

11、性：因為因為2525* *排序后仍然在排序后仍然在2525的后面的后面12void InsertSort ( SqList &L ) /對順序表對順序表L作直接插入排序作直接插入排序 for ( i = 2; i =L.length; + i ) /直接在原始無序表直接在原始無序表L中排序中排序 if (L.ri.key L.ri-1.key) /若若L.ri較小則插入有序子表內(nèi)較小則插入有序子表內(nèi) L.r0= L.ri; /先將待插入的元素放入先將待插入的元素放入“哨兵哨兵”位置位置 L.ri= L.ri-1; /子表元素開始后移子表元素開始后移 for ( j=i-2; L.r0.

12、key L.rj.key; -j ) L.rj+1= L.rj; /只要子表元素比哨兵大就不斷后移只要子表元素比哨兵大就不斷后移L.rj+1= L.r0; /直到子表元素小于哨兵，將哨兵值送入直到子表元素小于哨兵，將哨兵值送入 /當前要插入的位置（包括插入到表首）當前要插入的位置（包括插入到表首） /if/ InsertSort （參見教材（參見教材P265P265）13優(yōu)點：優(yōu)點：比較次數(shù)大大減少，全部元素比較次數(shù)僅為比較次數(shù)大大減少，全部元素比較次數(shù)僅為O O( (n nloglog2 2n)n)。時間效率：時間效率：雖然比較次數(shù)大大減少，可惜移動次數(shù)并未減少，雖然比較次數(shù)大大減少，可惜移

13、動次數(shù)并未減少， 所以排序效率仍為所以排序效率仍為O(nO(n2 2) ) ?？臻g效率：空間效率：仍為仍為 O O（1 1）穩(wěn)穩(wěn) 定定 性：性： 穩(wěn)定穩(wěn)定一個容易想到的改進方法：一個容易想到的改進方法： 能否減少移動次數(shù)？能否減少移動次數(shù)？ 既然子表有序且為順序存儲結(jié)構(gòu)，既然子表有序且為順序存儲結(jié)構(gòu)，則插入時采用則插入時采用折半查找折半查找定可加速。定可加速。14這是對折半插入排序的一種改進，其目的是減少排序過這是對折半插入排序的一種改進，其目的是減少排序過程中的移動次數(shù)。程中的移動次數(shù)。代價：代價：需要增加需要增加n n個記錄的輔助空間。個記錄的輔助空間。思路：思路：增開輔助數(shù)組增開輔助數(shù)組

14、d, d, 大小與大小與r r相同。相同。中值中值循環(huán)向量循環(huán)向量排序中途排序中途: d= ( 49，65，76, 97 ), ( 13, 27, 38 ）例：待排序列例：待排序列T=(49，38，65，97, 76, 13, 27, 49*，55, 04）finalfinalfirstfirst15討論：討論：若記錄是若記錄是鏈表結(jié)構(gòu)鏈表結(jié)構(gòu)，用直接插入排序行否？，用直接插入排序行否？答：答：行，而且無需移動元素，時間效率更高！行，而且無需移動元素，時間效率更高！自測卷上有對應的程序設(shè)計題。自測卷上有對應的程序設(shè)計題。161例：例：關(guān)鍵字序列關(guān)鍵字序列 T=(21，25，49，25*，16，

15、08），）， 請寫出表插入排序的具體實現(xiàn)過程。請寫出表插入排序的具體實現(xiàn)過程。解：解：假設(shè)該序列（結(jié)構(gòu)類型假設(shè)該序列（結(jié)構(gòu)類型) )已存入一維數(shù)組已存入一維數(shù)組r7r7中，將中，將r0r0作為表頭結(jié)點。則算法執(zhí)行過程為：作為表頭結(jié)點。則算法執(zhí)行過程為：i 關(guān)鍵字關(guān)鍵字 ri.key ri.link0 1212253494 25*516608指向第指向第1 1個元素個元素表頭結(jié)點表頭結(jié)點03002* *表示后一個表示后一個2525MaxNum17int LinkInsertSort (Linklist &L) L.r0.Key = MaxNum; L.r0. Link = 1; L.r1

16、.Link = 0; /先形成首元素的小循環(huán)鏈表先形成首元素的小循環(huán)鏈表for ( int i = 2; i = L.length; i+ ) int current = L.r0. Link; /current=/current=當前元素的游標當前元素的游標 int pre = 0; while ( L.rcurrent. Key = L.ri. Key) /若若i i元素比當前元素大元素比當前元素大 pre = current; /currentcurrent后移后移, , pre“pre“保護現(xiàn)場保護現(xiàn)場”，以利，以利i i元素元素后面插后面插入入 current = L.rcurren

17、t. Link; /繼續(xù)找繼續(xù)找i i元素的插入位置元素的插入位置L.ri. Link = current; / / 當當i i元素元素找到合適序位時，找到合適序位時，L.rpre. Link = i; /便在便在prepre與與currentcurrent之間插入之間插入 /for /LinkInsertSort18表插入排序算法分析：表插入排序算法分析： 無需移動記錄，只需修改無需移動記錄，只需修改2n次指針值。但由于比較次次指針值。但由于比較次數(shù)沒有減少，故數(shù)沒有減少，故時間效率仍為時間效率仍為O(n2) 。 空間效率肯定低空間效率肯定低，因為增開了指針分量（但在運算過，因為增開了指針分

18、量（但在運算過程中沒有用到更多的輔助單元）。程中沒有用到更多的輔助單元）。 穩(wěn)定性：穩(wěn)定性：25和和25*排序前后次序未變，排序前后次序未變，穩(wěn)定穩(wěn)定。注：注：此算法得到的只是一個有序鏈表，查找記錄時只能滿此算法得到的只是一個有序鏈表，查找記錄時只能滿足順序查找方式。足順序查找方式。改進：改進：可以根據(jù)表中指針線索，很快對所有記錄重排，形可以根據(jù)表中指針線索，很快對所有記錄重排，形成成真正的有序表（順序存儲方式），從而能滿足折半真正的有序表（順序存儲方式），從而能滿足折半查找方式。查找方式。具體實現(xiàn)見教材具體實現(xiàn)見教材P269。19子序列的構(gòu)成不是簡單地子序列的構(gòu)成不是簡單地“逐段分割逐段分割

19、”，而是將，而是將相隔某個增量相隔某個增量dkdk的記錄組成一個子序列的記錄組成一個子序列, ,讓增量讓增量dkdk逐趟縮逐趟縮短（例如依次取短（例如依次取5,3,15,3,1），直到），直到dkdk1 1為止。為止。2038例：例：關(guān)鍵字序列關(guān)鍵字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），），請寫出希爾排序的具體實現(xiàn)過程。請寫出希爾排序的具體實現(xiàn)過程。0123456789104938659776132749*5504初態(tài)：初態(tài)：第第1趟趟 (dk=5)第第2趟趟 (dk=3)第第3趟趟 (dk=1)4913134938276549*97557604

20、2738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 算法分析：算法分析：開始時開始時dk 的值較大，子序列中的對象較少，排序速度的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，較快；隨著排序進展，dk 值逐漸變小，子序列中對象個數(shù)值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。所以排序速度仍然很快。21時間效率：時間效率：空間效

21、率：空間效率：因為僅占用因為僅占用1 1個緩沖單元個緩沖單元算法的穩(wěn)定性：算法的穩(wěn)定性：因為因為4949* *排序后卻到了排序后卻到了4949的前面的前面由經(jīng)驗公式得到由經(jīng)驗公式得到練練1. 欲將序列（欲將序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼）中的關(guān)鍵碼按字母升序重排，則初始步長為按字母升序重排，則初始步長為4的希爾排序一趟的結(jié)果是？的希爾排序一趟的結(jié)果是？答：答：原始序列：原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shellshell一趟后：一趟后：課堂練習：課堂練習：P,Q,R,A,D,H,C,F,M

22、,S,X ,Y22原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，694694，129129，937937，863863，742742，751751，076076，4384382562

23、56，301301，694694，076076，937937，863863，742742，751751，129129，438438256256，301301，694694，076076，438438，863863，742742，751751，129129，937937第第1趟趟dkdk=5=5第第2趟趟dkdk=3=3第第3趟趟dkdk=1=1256256，301301，694694，076076，438438，863863，742742，751751，129129，937937256256，301301，694694，076076，438438，863863，742742，751751，12

24、9129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301

25、，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，129129，256256，301301，438438，694694，742742，751751，863863，937937練練2. 以關(guān)鍵字序列（以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行希爾排序（）為例，寫出執(zhí)行希爾排序（取取dk=5, 3, 1）算）算法的法的各趟

26、各趟排序結(jié)束時，關(guān)鍵字序列的狀態(tài)。排序結(jié)束時，關(guān)鍵字序列的狀態(tài)。23void ShellSort(SqList &L，int dlta ，int t) /按增量序列按增量序列dlta0t-1對順序表對順序表L作作Shell排序排序 for(k=0；kt；+k) ShellInsert(L，dltak)； / ShellSort參見教材參見教材P272P272dkdk值依次裝在值依次裝在dltadltat t 中中/增量為增量為dltak的一趟插入排序的一趟插入排序24理解難點：與前面的演示不同，理解難點：與前面的演示不同，并不提前處理并不提前處理i i子子集后部元素，每次只考慮子集的前

27、部（集后部元素，每次只考慮子集的前部（j=j-dkj=j-dk）第二輪也只考慮第二輪也只考慮i+1i+1那個子集的前部。那個子集的前部。 for(i=dk+1；i=L.length； + i) if(ri.key 0&(r0.key0&(r0.keyrj.key); j-=dk) rj+dk=rj；rj+dk=r0； 5 7 45 7 4 i=1 i+dk i=1 i+dk=6 i+2dk=11 =6 i+2dk=11 如果不用如果不用forfor循環(huán)，比較的結(jié)果是循環(huán)，比較的結(jié)果是 5 5，4 4，7 7 只有執(zhí)行只有執(zhí)行forfor循環(huán)后，比較結(jié)果才會是循環(huán)后，比較結(jié)果才會

28、是 4 4，5 5，7 7for(i=dk+1；i=L.length； + i) if(ri.key ri-dk.key) r0=ri；大者后移大者后移2610.3 10.3 交換排序交換排序交換排序的主要算法有：交換排序的主要算法有： 1) 冒泡排序冒泡排序 2) 快速排序快速排序27 1) 基本思路：基本思路：每趟不斷將記錄兩兩比較，并按每趟不斷將記錄兩兩比較，并按“前小后大前小后大”（或（或“前大后小前大后小”）規(guī)則交換。）規(guī)則交換。優(yōu)點：優(yōu)點：每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能還能同時部分理順其他元素同時部分理順其他元素；一

29、旦下趟沒有交換發(fā)；一旦下趟沒有交換發(fā)生，還可以生，還可以提前結(jié)束排序提前結(jié)束排序。前提：前提：順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 例：例：關(guān)鍵字序列關(guān)鍵字序列 T=(21，25，49，25*，16，08），請寫出），請寫出冒泡排序的具體實現(xiàn)過程。冒泡排序的具體實現(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)：初態(tài)：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟一定要附設(shè)交換標志！一定要附

30、設(shè)交換標志！28冒泡排序的算法分析冒泡排序的算法分析最好情況：最好情況：初始排列已經(jīng)有序，只執(zhí)行一趟起泡，做初始排列已經(jīng)有序，只執(zhí)行一趟起泡，做 n- -1 次關(guān)鍵碼比較，不移動對象。次關(guān)鍵碼比較，不移動對象。最壞情形：最壞情形：初始排列逆序，初始排列逆序，算法要執(zhí)行算法要執(zhí)行n-1 1趟起泡，第趟起泡，第i趟趟(1 i n) 做了做了n- i 次關(guān)鍵碼比較，執(zhí)行了次關(guān)鍵碼比較，執(zhí)行了n-i 次對象交換。次對象交換。此時的比較總次數(shù)此時的比較總次數(shù)KCN和記錄移動次數(shù)和記錄移動次數(shù)RMN為：為：11111233121nininninRMNnninKCN)()()()(2930303131( )

31、，設(shè)以首元素為樞軸中心設(shè)以首元素為樞軸中心例例1：關(guān)鍵字序列關(guān)鍵字序列 T=(21，25，49，25*，16，08），請），請寫出快速排序的算法步驟。寫出快速排序的算法步驟。21， 25， 49， 25*，16， 08初態(tài)：初態(tài)：第第1趟：趟：第第2趟：趟：第第3趟：趟：08，16，21，25， 25*，(49)2116，08，( )25，25*，49(08)，16，21，25，(25*，49)3232pivotkeypivotkey=21=21( 08 ，16 ） 21 （ 25* ， 49， 25 ）Low=high=Low=high=3 3，本趟停止，將本趟停止，將中樞點定位并返回位置信

32、息中樞點定位并返回位置信息例例2：關(guān)鍵字序列關(guān)鍵字序列 T=(21，25，49，25*，16，08），計算），計算機如何實現(xiàn)快速排序算法的某一趟過程？機如何實現(xiàn)快速排序算法的某一趟過程？ri0123456初態(tài)初態(tài)21254925*1608第第1趟趟highhighlowlow2125*321082516492525* *跑到了前面，跑到了前面，不穩(wěn)定不穩(wěn)定！設(shè)計技巧：設(shè)計技巧：交替交替/振蕩式逼近振蕩式逼近3333例例3：以關(guān)鍵字序列（以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行快速算法的各趟排序）為例，寫出執(zhí)行快速算法的各趟排序

33、結(jié)束時，關(guān)鍵字序列的狀態(tài)。結(jié)束時，關(guān)鍵字序列的狀態(tài)。原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438第第1趟趟第第2趟趟第第3趟趟第第4趟趟256256，301301，751751，129129，937937，863863，742742，694694，076076，438438，129129，937937，863863，742742，694694，301301，438438要求按算法上機實現(xiàn)步驟要求按算法上機實現(xiàn)步驟076076301301129129751751，129129，43

34、8438，301301，694694，742742，694694，863863，937937，301301，694694，742742，937937，301301，301301，694694，742742，937937，742742，因為每趟確定的元素呈指數(shù)增加因為每趟確定的元素呈指數(shù)增加( (存每層存每層lowlow，highhigh和和pivot)pivot)因為有跳躍式交換。因為有跳躍式交換。3434討論討論1 1：如何編程實現(xiàn)？如何編程實現(xiàn)？分析：分析：每一趟子表的形成是采用從兩頭向中間交替式逼近法；每一趟子表的形成是采用從兩頭向中間交替式逼近法；由于每趟中對各子表的操作都相似，主程序

35、可采用遞歸算法。由于每趟中對各子表的操作都相似，主程序可采用遞歸算法。見教材見教材P275intint (SqList &L,int(SqList &L,int low low,int,int high high) ) /一趟快排一趟快排/交換子表交換子表 rlowrlowhighhigh的記錄，使支點（樞軸）記錄到位，并的記錄，使支點（樞軸）記錄到位，并返回其位置返回其位置。返回時，在支點之前的記錄均不大于它，支點之后的記錄均不小于它。返回時，在支點之前的記錄均不大于它，支點之后的記錄均不小于它。 r0=r0=rlowrlow ; ; /以子表的首記錄作為支點記錄，放入以子表

36、的首記錄作為支點記錄，放入r0r0單元單元（續(xù)下頁）（續(xù)下頁）一趟快速排序算法一趟快速排序算法（針對一個子表的操作）（針對一個子表的操作）3535pivotkeypivotkey= =rlow.keyrlow.key; ; /取支點的關(guān)鍵碼存入取支點的關(guān)鍵碼存入pivotkeypivotkey變量變量while(lowwhile(low high) high)/從表的兩端交替地向中間掃描從表的兩端交替地向中間掃描 while(while(lowlowhigh=pivotkeyrhigh.key=pivotkey ) ) rlow=rhigh rlow=rhigh; ; /比支點小的記錄交換到低

37、端；比支點小的記錄交換到低端； while(while(lowlowhighhigh & & rlow.key=pivotkeyrlow.key=pivotkey) ) rhigh=rlow rhigh=rlow; /比支點大的記錄交換到高端；比支點大的記錄交換到高端；rlowrlow=r0;=r0; /支點記錄到位；支點記錄到位；return return lowlow; ; /返回支點記錄所在位置。返回支點記錄所在位置。 /Partition/Partition3636從從高端高端掃描掃描尋找小于尋找小于pivot的元素的元素從從低端低端掃描掃描尋找大于尋找大于pivot的

38、元素的元素一趟快速排序算法流程圖一趟快速排序算法流程圖r0=rlow; pivot=rlow.key;low highlow =pivot- high;rlow = rhigh;low high &rlow.key=pivot- low;rhigh = rlow;rlow = r0;return low3737if ( low 1 /對順序表對順序表L中的子序列中的子序列r lowhigh 作快速排序作快速排序/一趟快排，將一趟快排，將r 一分為二一分為二/在左子區(qū)間進行遞歸快排，直到長度為在左子區(qū)間進行遞歸快排，直到長度為1/在右子區(qū)間進行遞歸快排，直到長度為在右子區(qū)間進行遞歸快排，

39、直到長度為1是局部變量是局部變量 1, L.length 對順序表對順序表L進行快速排進行快速排序的操作函數(shù)為：序的操作函數(shù)為：3838設(shè)每個子表的支點都在中間（比較均衡），則：設(shè)每個子表的支點都在中間（比較均衡），則：第第1 1趟比較，可以確定趟比較，可以確定1 1個元素的位置；個元素的位置；第第2 2趟比較（趟比較（2 2個子表），可以再確定個子表），可以再確定2 2個元素的位置；個元素的位置；第第3 3趟比較（趟比較（4 4個子表），可以再確定個子表），可以再確定4 4個元素的位置；個元素的位置；第第4 4趟比較（趟比較（8 8個子表），可以再確定個子表），可以再確定8 8個元素的位置；

40、個元素的位置； 只需只需 loglog2 2n n 1 1趟便可排好序。趟便可排好序?；旧鲜?，因為每趟可以確定的數(shù)據(jù)元素是呈指數(shù)增加的?；旧鲜?，因為每趟可以確定的數(shù)據(jù)元素是呈指數(shù)增加的。而且，每趟需要比較和移動的元素也呈指數(shù)下降，加上編程而且，每趟需要比較和移動的元素也呈指數(shù)下降，加上編程時使用了交替逼近技巧，更進一步減少了移動次數(shù)，所以速度時使用了交替逼近技巧，更進一步減少了移動次數(shù)，所以速度特別快。特別快。教材教材P276P276有證明：快速排序的平均排序效率為有證明：快速排序的平均排序效率為O(nlogO(nlog2 2n)n)；但最壞情況下但最壞情況下( (例如天然有序例如天然有序) )仍為仍為O(nO(n2 2),),改進措施見改進措施見P277P277。3939選擇排序有多種具體實現(xiàn)算法：選擇排序有多種具體實現(xiàn)算法： 1) 簡單選擇排序簡單選擇排序 2) 錦標賽排序錦標賽排序 3) 堆排序堆排序40404141例：例：關(guān)鍵字序列關(guān)鍵字序列T= （21，25，4