嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)排序演示文稿

嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)排序演示文稿當(dāng)前第1頁\共有59頁\編于星期四\16點(diǎn)嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)排序當(dāng)前第2頁\共有59頁\編于星期四\16點(diǎn)9.1插入排序直接插入排序排序過程：整個排序過程為n-1趟插入，即先將序列中第1個記錄看成是一個有序子序列，然后從第2個記錄開始，逐個進(jìn)行插入，直至整個序列有序算法描述當(dāng)前第3頁\共有59頁\編于星期四\16點(diǎn)例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序結(jié)果：

01234567

當(dāng)前第4頁\共有59頁\編于星期四\16點(diǎn)算法評價時間復(fù)雜度若待排序記錄按關(guān)鍵字從小到大排列(正序)關(guān)鍵字比較次數(shù)：記錄移動次數(shù)：

01234567

13273849657697當(dāng)前第5頁\共有59頁\編于星期四\16點(diǎn)若待排序記錄按關(guān)鍵字從大到小排列(逆序)關(guān)鍵字比較次數(shù)：記錄移動次數(shù)：

01234567

97766549382713當(dāng)前第6頁\共有59頁\編于星期四\16點(diǎn)若待排序記錄是隨機(jī)的，取平均值關(guān)鍵字比較次數(shù)：記錄移動次數(shù)：T(n)=O(n2)空間雜度：S(n)=O(1)當(dāng)前第7頁\共有59頁\編于星期四\16點(diǎn)折半插入排序排序過程：用折半查找方法確定插入位置的排序叫~例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)當(dāng)前第8頁\共有59頁\編于星期四\16點(diǎn)算法描述算法評價時間復(fù)雜度：T(n)=O(n2)空間復(fù)雜度：S(n)=O(1)當(dāng)前第9頁\共有59頁\編于星期四\16點(diǎn)希爾排序(縮小增量法)排序過程：先取一個正整數(shù)d1<n，把所有相隔d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2<d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進(jìn)一個組中排序為止當(dāng)前第10頁\共有59頁\編于星期四\16點(diǎn)取d3=1三趟分組：1344838274955659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d1=5一趟分組：49

38

65

97

76

13

27

48

55

4取d2=3二趟分組：13

27

48

55

4

49

38

65

97

76當(dāng)前第11頁\共有59頁\編于星期四\16點(diǎn)算法描述例4938659776132748554#defineT3intd[]={5,3,1};ji49133827一趟排序：1327485544938659776jiji274jiji5538jijiji二趟排序：13

4

48

38

27

49

55

65

97

76jiji6548ji9755ji764123456789101234567891012345678910當(dāng)前第12頁\共有59頁\編于星期四\16點(diǎn)希爾排序特點(diǎn)子序列的構(gòu)成不是簡單的“逐段分割”，而是將相隔某個增量的記錄組成一個子序列希爾排序可提高排序速度，因為分組后n值減小，n2更小，而T(n)=O(n2),所以T(n)從總體上看是減小了關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為1的插入排序時，序列已基本有序增量序列取法沒有除1以外的公因子最后一個增量值必須為1當(dāng)前第13頁\共有59頁\編于星期四\16點(diǎn)9.2快速排序冒泡排序排序過程將第一個記錄的關(guān)鍵字與第二個記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止——第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個記錄上對前n-1個記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個記錄位置重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行過交換記錄的操作”為止當(dāng)前第14頁\共有59頁\編于星期四\16點(diǎn)例4938659776132730初始關(guān)鍵字3849657613273097第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟3849769713972797309713767676273013652765306513134949304927382738303812345678當(dāng)前第15頁\共有59頁\編于星期四\16點(diǎn)算法描述算法評價時間復(fù)雜度最好情況（正序）比較次數(shù)：n-1移動次數(shù)：0最壞情況（逆序）比較次數(shù)：移動次數(shù)：空間復(fù)雜度：S(n)=O(1)T(n)=O(n2)當(dāng)前第16頁\共有59頁\編于星期四\16點(diǎn)快速排序基本思想：通過一趟排序，將待排序記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄進(jìn)行排序，以達(dá)到整個序列有序當(dāng)前第17頁\共有59頁\編于星期四\16點(diǎn)排序過程：對r[s……t]中記錄進(jìn)行一趟快速排序，附設(shè)兩個指針i和j，設(shè)樞軸記錄rp=r[s]，x=rp.key初始時令i=s,j=t首先從j所指位置向前搜索第一個關(guān)鍵字小于x的記錄，并和rp交換再從i所指位置起向后搜索，找到第一個關(guān)鍵字大于x的記錄，和rp交換重復(fù)上述兩步，直至i==j為止再分別對兩個子序列進(jìn)行快速排序，直到每個子序列只含有一個記錄為止當(dāng)前第18頁\共有59頁\編于星期四\16點(diǎn)例初始關(guān)鍵字：4938659776132750ijxji完成一趟排序：(273813)49(76976550)分別進(jìn)行快速排序：(13)27(38)49(5065)76(97)快速排序結(jié)束：13273849

506576974927ijijij4965ji1349ij4997ij當(dāng)前第19頁\共有59頁\編于星期四\16點(diǎn)例初始關(guān)鍵字：4938659776132750ijx.key=49ji完成一趟排序：(273813)49(76976550)27ijijij65ji13ij4997ij算法描述當(dāng)前第20頁\共有59頁\編于星期四\16點(diǎn)算法評價時間復(fù)雜度最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n2)空間復(fù)雜度：需棧空間以實(shí)現(xiàn)遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(log2n)T(n)=O(n2)當(dāng)前第21頁\共有59頁\編于星期四\16點(diǎn)9.3選擇排序簡單選擇排序排序過程首先通過n-1次關(guān)鍵字比較，從n個記錄中找出關(guān)鍵字最小的記錄，將它與第一個記錄交換再通過n-2次比較，從剩余的n-1個記錄中找出關(guān)鍵字次小的記錄，將它與第二個記錄交換重復(fù)上述操作，共進(jìn)行n-1趟排序后，排序結(jié)束當(dāng)前第22頁\共有59頁\編于星期四\16點(diǎn)例初始：[49386597761327]kjjjjjjkki=11349一趟：13[386597764927]i=2kkjjjjj2738二趟：13

27[6597764938]三趟：13

27

38[97764965]四趟：13

27

38

49[769765]五趟：13

27

38

49

65[9776]六趟：13

27

38

49

65

76[97]排序結(jié)束：13

27

38

49

65

76

97當(dāng)前第23頁\共有59頁\編于星期四\16點(diǎn)算法描述算法評價時間復(fù)雜度記錄移動次數(shù)最好情況：0最壞情況：3(n-1)比較次數(shù)：空間復(fù)雜度：S(n)=O(1)T(n)=O(n2)當(dāng)前第24頁\共有59頁\編于星期四\16點(diǎn)堆排序堆的定義：n個元素的序列(k1,k2,……kn)，當(dāng)且僅當(dāng)滿足下列關(guān)系時，稱之為堆或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1例（96，83，27，38，11，9）例（13，38，27，50，76，65，49，97）962791138831327384965765097可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中n個元素的最小值或最大值當(dāng)前第25頁\共有59頁\編于星期四\16點(diǎn)堆排序：將無序序列建成一個堆，得到關(guān)鍵字最?。ɑ蜃畲螅┑挠涗洠惠敵龆秧?shù)淖钚。ù螅┲岛螅故Ｓ嗟膎-1個元素重又建成一個堆，則可得到n個元素的次小值；重復(fù)執(zhí)行，得到一個有序序列，這個過程叫~堆排序需解決的兩個問題：如何由一個無序序列建成一個堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個新的堆？第二個問題解決方法——篩選方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，若根結(jié)點(diǎn)值小于子樹的根結(jié)點(diǎn)值則與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”當(dāng)前第26頁\共有59頁\編于星期四\16點(diǎn)例13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13273849502765769713輸出：13276549502738769713輸出：132738當(dāng)前第27頁\共有59頁\編于星期四\16點(diǎn)4965502738769713輸出：1327387665502738499713輸出：132738495065762738499713輸出：132738499765762738495013輸出：13273849506597762738495013輸出：13273849509765762738495013輸出：132738495065當(dāng)前第28頁\共有59頁\編于星期四\16點(diǎn)7665972738495013輸出：1327384950659765762738495013輸出：132738495065769765762738495013輸出：1327384950657697當(dāng)前第29頁\共有59頁\編于星期四\16點(diǎn)算法描述第一個問題解決方法方法：按關(guān)鍵字的初始序列建立一棵完全二叉樹，然后從無序序列的第n/2個元素（即此無序序列對應(yīng)的完全二叉樹的最后一個非終端結(jié)點(diǎn)）起，至第一個元素止，進(jìn)行反復(fù)篩選當(dāng)前第30頁\共有59頁\編于星期四\16點(diǎn)例含8個元素的無序序列（49，38，65，97，76，13，27，50）4965382713769750496538271376509749133827657650974913382765765097132738496576509712345678493865977613275050971365381327494913382765765097當(dāng)前第31頁\共有59頁\編于星期四\16點(diǎn)算法描述算法評價時間復(fù)雜度：最壞情況下T(n)=O(nlogn)空間復(fù)雜度：S(n)=O(1)當(dāng)前第32頁\共有59頁\編于星期四\16點(diǎn)9.4歸并排序歸并——將兩個或兩個以上的有序表組合成一個新的有序表，叫~2-路歸并排序排序過程設(shè)初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列長度為1兩兩合并，得到n/2個長度為2或1的有序子序列再兩兩合并，……如此重復(fù)，直至得到一個長度為n的有序序列為止當(dāng)前第33頁\共有59頁\編于星期四\16點(diǎn)將下屬兩個已排序的順序表合并成一個有序表。順序比較兩者的相應(yīng)元素，小者移入另一表中，反復(fù)如此，直至其中任一表都移入另一表為止。0123 44913659776780AB0123 4567Cijk當(dāng)前第34頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk7當(dāng)前第35頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk7當(dāng)前第36頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk713當(dāng)前第37頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk71349當(dāng)前第38頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk71349當(dāng)前第39頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk7134965當(dāng)前第40頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk7134965當(dāng)前第41頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk713496576當(dāng)前第42頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk713496576當(dāng)前第43頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk71349657680當(dāng)前第44頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk71349657680當(dāng)前第45頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk71349657680至此B表的元素都已移入C表，只需將A表的剩余部分移入C表即可。當(dāng)前第46頁\共有59頁\編于星期四\16點(diǎn)0123 44913659776780AB0123 4567Cijk71349657680至此B表的元素都已移入C表，只需將A表的剩余部分移入C表即可。97當(dāng)前第47頁\共有59頁\編于星期四\16點(diǎn)例初始關(guān)鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：[13273849657697]當(dāng)前第48頁\共有59頁\編于星期四\16點(diǎn)算法描述算法評價時間復(fù)雜度：T(n)=O(nlog2n)空間復(fù)雜度：S(n)=O(n)當(dāng)前第49頁\共有59頁\編于星期四\16點(diǎn)9.5基數(shù)排序多關(guān)鍵字排序定義：例對52張撲克牌按以下次序排序：2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A兩個關(guān)鍵字：花色（<<<）面值（2<3<……<A）并且“花色”地位高于“面值”當(dāng)前第50頁\共有59頁\編于星期四\16點(diǎn)多關(guān)鍵字排序方法最高位優(yōu)先法（MSD)：先對最高位關(guān)鍵字k1（如花色）排序，將序列分成若干子序列，每個子序列有相同的k1值；然后讓每個子序列對次關(guān)鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至就每個子序列對最低位關(guān)鍵字kd排序；最后將所有子序列依次連接在一起成為一個有序序列當(dāng)前第51頁\共有59頁\編于星期四\16點(diǎn)最低位優(yōu)先法(LSD)：從最低位關(guān)鍵字kd起進(jìn)行排序，然后再對高一位的關(guān)鍵字排序，……依次重復(fù)，直至對最高位關(guān)鍵字k1排序后，便成為一個有序序列MSD與LSD不同特點(diǎn)按MSD排序，必須將序列逐層分割成若干子序列，然后對各子序列分別排序按LSD排序，不必分成子序列，對每個關(guān)鍵字都是整個序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實(shí)現(xiàn)排序當(dāng)前第52頁\共有59頁\編于星期四\16點(diǎn)鏈?zhǔn)交鶖?shù)排序基數(shù)排序：借助“分配”和“收集”對單邏輯關(guān)鍵字進(jìn)行排序的一種方法鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲結(jié)構(gòu)的基數(shù)排序當(dāng)前第53頁\共有59頁\編于星期四\16點(diǎn)鏈?zhǔn)交鶖?shù)排序步驟設(shè)置10個隊列，f[i]和e[i]分別為第i個隊列的頭指針和尾指針第一趟分配對最低位關(guān)鍵字（個位）進(jìn)行，改變記錄的指針值，將鏈表中記錄分配至10個鏈隊列中，每個隊列記錄的關(guān)鍵字的個位相同第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的隊頭記錄，重新將10個隊列鏈成一個鏈表重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集，分別對十位、百位進(jìn)行，最后得到一個有序序列當(dāng)前第54頁\共有5