數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT

第八章排序技術(shù)本章的基本內(nèi)容是：排序的基本概念插入排序交換排序選擇排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第1頁。8.1概述

排序：將一組“無序”的記錄序列,調(diào)整為按關(guān)鍵字“有序”的記錄序列.學(xué)號姓名高數(shù)英語思想品德0002王軍85880001李明64920003湯曉影8586………687278……1.排序的基本概念數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第2頁。排序：給定一組記錄的集合{r1,r2,……,rn}，其相應(yīng)的關(guān)鍵碼分別為{k1,k2,……,kn}，排序是將這些記錄排列成順序?yàn)閧rs1,rs2,……,rsn}的一個(gè)序列，使得相應(yīng)的關(guān)鍵碼滿足非遞減關(guān)系ks1≤ks2≤……≤ksn（稱為升序）或非遞增關(guān)系ks1≥ks2≥……≥ksn（稱為降序）。1.排序的基本概念學(xué)號姓名高數(shù)英語0002李明640001王軍850003湯曉影85………726878…學(xué)號姓名高數(shù)英語0001王軍850002李明640003湯曉影85………687278…8.1概述

數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第3頁。假定在待排序的記錄集中，存在多個(gè)具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri一定在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

學(xué)號姓名高數(shù)英語思想品德0001王軍85880002李明64920003湯曉影8586………687278……排序算法的穩(wěn)定性：8.1概述

1.排序的基本概念數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第4頁。待排序序列中的記錄已按關(guān)鍵碼排好序。待排序序列中記錄的排列順序與排好序的順序正好相反。學(xué)號姓名高數(shù)英語思想品德0001王軍85880002李明64920003湯曉影8586………687278……8.1概述

1.排序的基本概念正序：逆序（反序）：數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第5頁。排序的分類在排序的整個(gè)過程中，待排序的所有記錄全部被放置在內(nèi)存中,不需要訪問外存由于待排序的記錄個(gè)數(shù)太多，不能同時(shí)放置在內(nèi)存，而需要將一部分記錄放置在內(nèi)存，另一部分記錄放置在外存上，整個(gè)排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。8.1概述

1.排序的基本概念1.內(nèi)排序：2.外排序：數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第6頁。2.內(nèi)排序算法1.插入排序2.交換排序3.選擇排序4.歸并排序直接插入排序希爾排序冒泡排序快速排序簡單選擇排序堆排序8.1概述

數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第7頁。排序基本過程:是一個(gè)逐步擴(kuò)大記錄的有序序列長度的過程3.排序的基本過程有序序列區(qū)無序序列區(qū)有序序列區(qū)無序序列區(qū)一趟排序一趟排序:將無序序列區(qū)里一個(gè)或幾個(gè)記錄合并到有序序列的過程為一趟排序，有序序列長度增加1個(gè)或幾個(gè)8.1概述

數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第8頁。大家有疑問的，可以詢問和交流可以互相討論下，但要小聲點(diǎn)數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第9頁。4.排序算法的存儲結(jié)構(gòu)從操作角度看，排序是線性結(jié)構(gòu)的一種操作，待排序記錄可以用順序存儲結(jié)構(gòu)或鏈接存儲結(jié)構(gòu)存儲。假定2：將待排序的記錄序列排序?yàn)樯蛐蛄小?/p>

r[n+1]假定1：待排序記錄采用順序存儲結(jié)構(gòu)，關(guān)鍵碼為整型，且記錄只有關(guān)鍵碼一個(gè)數(shù)據(jù)項(xiàng)。8.1概述

101524612354098012345678數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第10頁。內(nèi)排序算法1.插入排序2.交換排序3.選擇排序4.歸并排序直接插入排序希爾排序冒泡排序快速排序簡單選擇排序堆排序8.1概述

數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第11頁。8.2插入排序插入排序的主要操作是插入，其基本思想是：每次將一個(gè)待排序的記錄按其關(guān)鍵碼的大小插入到一個(gè)已經(jīng)排好序的有序序列中，直到全部記錄排好序?yàn)橹?。舉例:有序序列2,待排序記錄3,6,11）直接插入排序2）希爾排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第12頁?；舅枷耄涸诓迦氲趇（i＞1）個(gè)記錄時(shí)，前面的i-1個(gè)記錄已經(jīng)排好序。8.2.1直接插入排序有序序列無序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……有序序列無序序列8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第13頁。直接插入排序過程示例

r0123456211825221025*21第一趟18221025*252522212522211025*2522211025*2522211810181025*第二趟18第四趟1825*第三趟第五趟算法穩(wěn)定嗎？21算法思想？i從第2個(gè)數(shù)到第n個(gè)數(shù){將第i個(gè)數(shù)插入到有序序列中的合理位置}8.2插入排序共多少趟？數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第14頁。對于r[i]，如何查找它的插入位置?如何實(shí)現(xiàn)插入？直接插入排序需解決的關(guān)鍵問題?無序序列2025211826……1)將r[i]暫存在r[0]2)j=i-1；//從第i-1記錄開始查找3)當(dāng)r[j]>r[0]時(shí)，循環(huán)做{r[j]后移一個(gè)位置,j--}4)r[j+1]=r[0]//將r[0]插入到位置j+12201234521ij25j22j218.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第15頁。直接插入排序無序序列2025101825……2201234510ij25222010jr[0]的作用?暫存單元,監(jiān)視哨對于r[i]，如何查找它的插入位置?如何實(shí)現(xiàn)插入？需解決的關(guān)鍵問題?1)將r[i]暫存在r[0]2)j=i-1；//從第i-1記錄開始查找3)當(dāng)r[j]>r[0]時(shí)，循環(huán)做{r[j]后移一個(gè)位置,j--}4)r[j+1]=r[0]//將r[0]插入到位置j+1jj8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第16頁。voidinsertSort(intr[],intn){ for(i=2;i<=n;i++){r[0]=r[i];for(j=i-1;r[0]<r[j];j--)

r[j+1]=r[j];r[j+1]=r[0]; }}直接插入排序算法1.i從第2個(gè)到第n個(gè)記錄,做以下循環(huán)：1.1將r[i]暫存在r[0]1.2j=i-1；1.3當(dāng)r[j]>r[0]時(shí)，循環(huán)做：{r[j]后移一個(gè)位置,j--}1.4r[j+1]=r[0]8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第17頁。直接插入排序過程示例

r0123456211825221025*212125i=218221025*25i=318221025*2225222110252221102525*2522211025*252221181018181025*i=418i=61825*i=525218.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第18頁。直接插入排序練習(xí)

125920631248.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第19頁。直接插入排序練習(xí)

[12]592063124初始序列[512]92063124第一趟[5912]2063124第二趟[591220]63124第三趟[5691220]3124第四趟第五趟[569122031]24第六趟[56912202431]8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第20頁。1.基本操作。內(nèi)排序在排序過程中的基本操作：⑴比較：關(guān)鍵碼之間的比較；⑵移動：記錄從一個(gè)位置移動到另一個(gè)位置。2.輔助存儲空間。輔助存儲空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存放待排序記錄占用的存儲空間之外，執(zhí)行算法所需要的其他存儲空間。3.算法本身的復(fù)雜程度。

排序算法的性能8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第21頁。直接插入排序算法性能分析最好情況下：

12345時(shí)間復(fù)雜度為O(n)。比較次數(shù)：n-1移動次數(shù)：2(n-1)123452123453123454123455（正序）8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第22頁。直接插入排序算法性能分析最好情況下（正序）：

比較次數(shù)：n-1移動次數(shù)：2(n-1)最壞情況下（逆序）：時(shí)間復(fù)雜度為O(n2)。54321453214345213234512123451比較次數(shù)：移動次數(shù)：2)1)(2(2-+=?=nnini2)1)(4(1-+=+?nnin2=i）（時(shí)間復(fù)雜度為O(n)。8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第23頁。平均情況下（隨機(jī)排列）：

直接插入排序算法性能分析時(shí)間復(fù)雜度為O(n2)。比較次數(shù)：移動次數(shù)：4)1)(4(-+=?nnn2=i4)1)(2(2-+=?=nnnii2（21+i）8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第24頁。空間性能：需要一個(gè)記錄的輔助空間。直接插入排序算法是一種穩(wěn)定的排序算法。直接插入排序算法性能分析直接插入排序算法簡單、容易實(shí)現(xiàn)，適用于待排序記錄基本有序或待排序記錄較小時(shí)。當(dāng)待排序的記錄個(gè)數(shù)較多時(shí)，大量的比較和移動操作使直接插入排序算法的效率降低。8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第25頁。8.2.2希爾排序改進(jìn)的著眼點(diǎn)：（1）由于直接插入排序算法簡單，在待排序記錄數(shù)量n較小時(shí)效率也很高。

（2）若待排序記錄按關(guān)鍵碼基本有序時(shí)，直接插入排序的效率可以大大提高；213543218.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第26頁。（1）應(yīng)如何分割待排序記錄，才能保證整個(gè)序列逐步向基本有序發(fā)展？（2）子序列內(nèi)如何進(jìn)行直接插入排序？需解決的關(guān)鍵問題?基本思想：將整個(gè)待排序記錄分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，對全體記錄進(jìn)行直接插入排序。8.2.2希爾排序201819,657,1322018196571328.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第27頁。8.2.2希爾排序子序列的構(gòu)成不能是簡單地“逐段分割”，而是將相距某個(gè)“增量”的記錄組成一個(gè)子序列。逐漸縮短“增量”，當(dāng)縮短為1時(shí)就是對全體記錄進(jìn)行排序。1026159182041110261591820411d=3基本思想：將整個(gè)待排序記錄分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，對全體記錄進(jìn)行直接插入排序。8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第28頁。希爾插入排序過程示例

1234567894021254925*16初始序列300813d=4212525*304908401613252125*300849131640d=21325210825*16304940252125*300813164049d=10825211325*16304049082513162125*403049每隔d-1個(gè)增量記錄分為一組每組內(nèi)采用直接插入排序8.2插入排序算法穩(wěn)定嗎？數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第29頁。解決方法：將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。增量應(yīng)如何取？希爾最早提出的方法是d1=n/2，di+1=di/2。關(guān)鍵問題(1)應(yīng)如何分割待排序記錄？算法描述：for(d=n/2;d>=1;d=d/2){以d為增量，進(jìn)行組內(nèi)直接插入排序；}8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第30頁。希爾插入排序過程示例

1234567894021254925*16初始序列300813d=4212525*304908401613252125*300849131640每隔d分為一組在整個(gè)序列中，前d個(gè)記錄分別是d個(gè)子序列中的第一個(gè)記錄，所以從第d+1個(gè)記錄開始進(jìn)行插入。for(i=d+1;i<=n;i++){}8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第31頁。希爾插入排序過程示例

1234567894021254925*16初始序列300813d=4212525*304908401613252125*300849131640每隔d分為一組將插入數(shù)據(jù)r[i]暫存入r[0]j=i-1當(dāng)r[j]>r[0]，循環(huán)做：{

r[j]后移一位

j--}r[0]插入到位置j+1將插入數(shù)據(jù)r[i]暫存入r[0]j=i-d當(dāng)r[j]>r[0]且j>0，循環(huán)做：{r[i]后移d位j=j-d;}r[0]插入到位置j+d直接插入排序：希爾排序：8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第32頁。解決方法：在插入記錄r[i]時(shí)，自r[i-d]起往前跳躍式（跳躍幅度為d）搜索待插入位置，并且r[0]只是暫存單元，不是哨兵。當(dāng)搜索位置＜0，表示插入位置已找到。在搜索過程中，記錄后移也是跳躍d個(gè)位置。在整個(gè)序列中，前d個(gè)記錄分別是d個(gè)子序列中的第一個(gè)記錄，所以從第d+1個(gè)記錄開始進(jìn)行插入。關(guān)鍵問題(2)子序列內(nèi)如何進(jìn)行直接插入排序？8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第33頁。算法描述：for(i=d+1;i<=n;i++)//將r[i]插入到所屬的子序列中{

r[0]=r[i];//暫存待插入記錄j=i-d;//j指向所屬子序列的最后一個(gè)記錄while(j>0&&r[0]<r[j]){r[j+d]=r[j];//記錄后移d個(gè)位置j=j-d;//比較同一子序列的前一個(gè)記錄}r[j+d]=r[0];}關(guān)鍵問題(2)子序列內(nèi)如何進(jìn)行直接插入排序？8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第34頁。voidShellSort(intr[],intn){for(d=n/2;d>=1;d=d/2)//以d為增量,組內(nèi)直接插入排序for(i=d+1;i<=n;i++)//將r[i]插入到所屬的子序列中{r[0]=r[i];//暫存待插入記錄j=i-d;//j指向所屬子序列的最后一個(gè)記錄while(j>0&&r[0]<r[j]){r[j+d]=r[j];//記錄后移d個(gè)位置j=j-d;//比較同一子序列的前一個(gè)記錄}r[j+d]=r[0];}}希爾插入排序8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第35頁。希爾排序練習(xí)

12592063124初始序列第一趟結(jié)果d=3第二趟結(jié)果d=2第三趟結(jié)果d=1125920631246592012312456912202431初始化：d=3，d=2d=18.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第36頁。希爾排序算法的時(shí)間性能希爾排序算法的時(shí)間性能是所取增量的函數(shù)，而到目前為止尚未有人求得一種最好的增量序列。研究表明，希爾排序的時(shí)間性能在O(n2)和O(nlog2n)之間。當(dāng)n在某個(gè)特定范圍內(nèi)，希爾排序所需的比較次數(shù)和記錄的移動次數(shù)約為O(n1.3)

。希爾排序不穩(wěn)定希爾排序開始時(shí)增量較大，每個(gè)子序列中的記錄個(gè)數(shù)較少，從而排序速度較快；當(dāng)增量較小時(shí)，雖然每個(gè)子序列中記錄個(gè)數(shù)較多，但整個(gè)序列已基本有序，排序速度也較快。

8.2插入排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第37頁。第八章排序技術(shù)本章的基本內(nèi)容是：排序的基本概念插入排序交換排序選擇排序歸并排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第38頁。交換排序的主要操作是交換，其主要思想是：在待排序列中選兩個(gè)記錄，將它們的關(guān)鍵碼相比較，如果反序（即排列順序與排序后的次序正好相反），則交換它們的存儲位置。

8.3交換排序反序則交換rirj1）冒泡排序2）快速排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第39頁。8.3.1起泡排序基本思想：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。

rj

rj+1ri+1≤……

≤rn-1≤rn

無序區(qū)有序區(qū)1≤j≤i-1已經(jīng)位于最終位置反序則交換8.3交換排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第40頁。05981269385381起泡排序過程示例

059812693853810598126938538105981269385381總共n-1趟一共做多少趟？for(i=1;i<=n-1;i++)for(j=1;j<=n-i;j++){if(r[j]>r[j+1])r[j]<->r[j+1];}第i趟的比較范圍：從1到（n-i）8.3交換排序1234567數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第41頁。05981269385381起泡排序過程示例

059812693853810598126938538105981269385381提問：一定需要做n-1趟？如果在一趟排序過程中沒有進(jìn)行過交換操作,則排序結(jié)束。8.3交換排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第42頁。解決方法：在每一趟起泡排序之前，令exchange的初值為0。在排序過程中，只要有記錄交換，用exchange記錄交換發(fā)生的位置。這樣，在一趟排序結(jié)束后，只有當(dāng)exchange的值不為0才需要繼續(xù)做下一趟冒泡排序。關(guān)鍵問題1)：如何判別起泡排序的結(jié)束？intexchange=n;while(exchange){exchange=0;

for(j=1;j<=n-i;j++){if(r[j]>r[j+1]){r[j]<->r[j+1];

exchange=j;}}for(i=1;i<=n-1;i++)for(j=1;j<=n-i;j++){if(r[j]>r[j+1])r[j]<->r[j+1];}8.3交換排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第43頁。05981269385381起泡排序過程示例

059812693853810598126938538105981269385381提問：每趟排序只能使待排序范圍減1嗎？8.3交換排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第44頁。05981269788130起泡排序過程示例

0598123069788105981230697881如果最后一次交換是(位置j)<->(位置j+1)，位置j以后的所有記錄均已經(jīng)有序，即下一趟的待排序范圍縮短為1到j(luò)jj+18.3交換排序j數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第45頁。關(guān)鍵問題2）：如何確定每趟起泡排序的范圍？解決方法：變量exchange記載的是這趟排序中最后一次交換的位置，而下一趟的排序范圍是1到exchange。intexchange=n;while(exchange){bound=exchange;exchange=0;

for(j=1;j<bound;j++){if(r[j]>r[j+1]){r[j]<->r[j+1];

exchange=j;}}intexchange=n;while(exchange){exchange=0;

for(j=1;j<=n-i;j++){if(r[j]>r[j+1]){r[j]<->r[j+1];

exchange=j;}}8.3交換排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第46頁。voidBubbleSort(intr[],intn){ exchange=n;//初始的排序范圍是所有記錄 while(exchange){

bound=exchange;exchange=0；for(j=1;j<bound;j++)if(r[j]>r[j+1]){r[j]←→r[j+1]； exchange=j；}}}起泡排序算法8.3交換排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第47頁。起泡排序練習(xí)

12592063124初始序列第一趟結(jié)果第二趟結(jié)果第三趟結(jié)果第四趟結(jié)果[591262024]31[596]12202431[56912202431][56]9122024318.3交換排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第48頁。起泡排序的時(shí)間性能分析最好情況：比較次數(shù)：n-1移動次數(shù)：012345時(shí)間復(fù)雜度為O(n)。123458.3交換排序（正序）數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第49頁。最壞情況（反序）：起泡排序的時(shí)間性能分析最好情況（正序）：比較次數(shù)：n-1移動次數(shù)：054321時(shí)間復(fù)雜度為O(n)；時(shí)間復(fù)雜度為O(n2)。43215321452134512345比較次數(shù)：移動次數(shù)：2)1(1-=?=nn(n-i)n-1i2)1(1-=?=n3n3(n-i)n-1i平均情況：時(shí)間復(fù)雜度為O(n2)。穩(wěn)定算法8.3交換排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第50頁。內(nèi)排序算法1.插入排序2.交換排序3.選擇排序4.歸并排序直接插入排序希爾排序冒泡排序快速排序簡單選擇排序堆排序8.1概述

數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第51頁。8.3.2快速排序首先選一個(gè)軸值（即比較的基準(zhǔn)），通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，前一部分記錄的關(guān)鍵碼均小于或等于軸值，后一部分記錄的關(guān)鍵碼均大于或等于軸值，然后分別對這兩部分重復(fù)上述方法，直到整個(gè)序列有序。舉例:38275550333049653027333850554965273033384950556527303338495055658.3交換排序算法思想：數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第52頁?？焖倥判虻幕舅枷擘湃绾芜x擇軸值？⑵如何實(shí)現(xiàn)分割（稱一次劃分）？⑶如何處理分割得到的兩個(gè)待排序子序列？⑷如何判別快速排序的結(jié)束？需解決的關(guān)鍵問題?舉例:382755503330496530273338505549658.3交換排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第53頁。選擇軸值的方法：1.使用第一個(gè)記錄的關(guān)鍵碼；2.選取序列中間記錄的關(guān)鍵碼；3.比較序列中第一個(gè)記錄、最后一個(gè)記錄和中間記錄的關(guān)鍵碼，取關(guān)鍵碼居中的作為軸值并調(diào)換到第一個(gè)記錄的位置；4.隨機(jī)選取軸值。關(guān)鍵問題⑴：如何選擇軸值？選取不同軸值的后果：決定兩個(gè)子序列的長度，期望子序列的長度最好相等。8.3交換排序舉例:38275550333049653027333850554965數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第54頁。2750384955關(guān)鍵問題⑵：如何實(shí)現(xiàn)一次劃分？每個(gè)數(shù)和軸值做比較，比軸值大的數(shù)放后面，比軸值小的數(shù)放前面。關(guān)鍵在于數(shù)和軸值交換，從前、后兩端開始，逐漸向中間軸值逼近的過程。8.3交換排序33275038495533數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第55頁。關(guān)鍵問題⑵：如何實(shí)現(xiàn)一次劃分？8.3交換排序1）當(dāng)軸值在前面時(shí)，從后往前掃描，后面數(shù)逐個(gè)和軸值比較，第一個(gè)比軸值小的數(shù)和軸值換，小的數(shù)放在軸值的前面，軸值就位于待排序區(qū)域的后面2）當(dāng)軸值在后面時(shí)，從前往后掃描，前面數(shù)逐個(gè)和軸值比較，第一個(gè)比軸值大的數(shù)和軸值換，大的數(shù)放在軸值的后面，軸值就位于待排序區(qū)域的前面3）當(dāng)掃描到軸值，軸值就完成了一次劃分275038495533275038495533每個(gè)數(shù)和軸值做比較，比軸值大的數(shù)放后面，比軸值小的數(shù)放前面。關(guān)鍵在于數(shù)和軸值交換，從前后兩端開始，逐漸向中間軸值逼近的過程。275038495533完成一次劃分O(n)數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第56頁。30652750384955ji3855關(guān)鍵問題⑵：如何實(shí)現(xiàn)一次劃分？jjiiijiji=0,j=n-11)j從后往前掃描,找比軸值小的第一個(gè)數(shù),和軸值交換2)i從前往后掃描,找比軸值大的第一個(gè)數(shù),和軸值交換8.3交換排序333038652750495533306527504933數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第57頁。關(guān)鍵問題⑵：如何實(shí)現(xiàn)一次劃分？i=0,j=n-11)j從后往前掃描,找比軸值小的第一個(gè)數(shù),和軸值交換2)i從前往后掃描,找比軸值大的第一個(gè)數(shù),和軸值交換直到i=j結(jié)束，完成一次劃分，即軸值的位置8.3交換排序3855ij306527504933j3833306527504955iji3850302733654955ijj數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第58頁。解決方法：設(shè)待劃分的序列是r[s]~r[t]，設(shè)參數(shù)i，j分別指向子序列左、右兩端的下標(biāo)s和t，令r[s]為軸值，（1）j從后向前掃描，直到r[j]<r[i]，將r[j]移動到r[i]的位置(r[j]與r[i]交換)，使關(guān)鍵碼?。ㄍS值相比）的記錄移動到前面去；（2）i從前向后掃描，直到r[i]＞r[j]，將r[i]移動到r[j]的位置(r[i]與r[j]交換)

，使關(guān)鍵碼大（同軸值比較）的記錄移動到后面去；（3）重復(fù)上述過程，直到i=j。關(guān)鍵問題⑵：如何實(shí)現(xiàn)一次劃分？8.3交換排序數(shù)據(jù)結(jié)構(gòu)及算法排序-PPT全文共117頁，當(dāng)前為第59頁。關(guān)鍵問題⑵：如何實(shí)現(xiàn)一次劃分？算法描述：intPartition(intr[],intfirst,intend){ i=first;j=end;//初始化while(i<j) {while(i<j&&r[i]<=r[j])j--；//右側(cè)掃描

if(i<j){r[i]←→r[j];i++;//將較小記錄交換到前面}while(i<j&&r[i]<=r[j])i++；//左側(cè)掃描if(i<j){r[j]←→r[i];j--;//將較大記錄交換到后面}}returni;//i為軸值的最終位置}1)j從后往前掃描,找比軸值小的第一個(gè)數(shù),和軸值交換2)i從前往后掃描,找比軸值大的第一個(gè)數(shù),和軸值交換直到i=j結(jié)束，完成一次劃分，即軸值的位置

3827551349