2013數(shù)據(jù)結(jié)構(gòu)史排序

1、北京化工大學(xué)北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系史晟輝史晟輝 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)32022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)42022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)52022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)62022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)7各趟排序結(jié)果各趟排序結(jié)果0 1 2 3 4 50 1 2 3 4 5 temp250 1 2 3 4 5 temp492022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)825*0 1 2 3 4 50 1 2 3 4 5 temp160 1 2 3 4 5 temp0820

2、22-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)916490 1 2 3 4 50 1 2 3 4 5 temp0 1 2 3 4 5 temp完成2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)102525*0 1 2 3 4 50 1 2 3 4 5 temp0 1 2 3 4 5 temp212022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)112022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)122022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)13111122142221nininnniRMNnnniKCN/)()( ,/)(222022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)142022-4-1北京化工

3、大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)15 for ( int i = 1; i n; i+) Left = 0; Right = i-1; temp = Vi; while ( Left = Right ) int mid = ( Left + Right )/2; if ( temp = Left; k- ) Vk+1 = Vk; VLeft = temp; 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)16 1122log1logninni算法分析算法分析 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)172022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)182022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)1

4、90 1 2 3 4 5492516084925*0821252125*162022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)200 1 2 3 4 5491625*0821252022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)210 1 2 3 4 52022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)22 for ( int j = i; j = gap; j = j-gap ) if ( temp Vj-gap ) Vj = Vj-gap; else break; 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)23 Vj = temp; gap = ( int ) ( gap / 2 ); 2022-

5、4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)242022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)252022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)260 1 2 3 4 52022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)270 1 2 3 4 52022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)28 Swap ( Vj-1, Vj );, /交換 exchange = 1; /標(biāo)志置為1,有交換 i+; 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)2911111233121nininninRMNnninKCN)()()()(2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)302022-4-1北京化工大學(xué)信息學(xué)

6、院 數(shù)據(jù)結(jié)構(gòu)312022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)32QuickSort ( List ) if ( List的長度大于的長度大于1) 將序列將序列List劃分為兩個(gè)子序列劃分為兩個(gè)子序列 LeftList 和和 Right List; QuickSort ( LeftList );QuickSort ( RightList ); 將兩個(gè)子序列將兩個(gè)子序列 LeftList 和和 RightList 合并為一個(gè)序列合并為一個(gè)序列List; 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)330 1 2 3 4 52022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)340 1 2 3 4 5

7、2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)35 QuickSort ( V, pivotpos+1, right ); 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)36int Partition ( SortData V , int low, int high ) int pivotpos = low; /基準(zhǔn)位置基準(zhǔn)位置 SortData pivot = Vlow; for ( int i = low+1; i = high; i+ ) if ( Vi link, p, q, r, s; head-link = NULL; while ( f != NULL ) /原始鏈表未掃描完原始

8、鏈表未掃描完 p = s = f; q = r = NULL; while ( p != NULL ) /掃描原始鏈表掃描原始鏈表, 尋找排序碼最大的結(jié)點(diǎn)尋找排序碼最大的結(jié)點(diǎn)*s if ( p-data s-data ) s = p; r = q; /記憶當(dāng)前找到的排序碼最大結(jié)點(diǎn)記憶當(dāng)前找到的排序碼最大結(jié)點(diǎn) q = p; p = p-link; 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)53 if ( s = f ) f = f -link;/排序碼最大結(jié)點(diǎn)是鏈表前端結(jié)點(diǎn)排序碼最大結(jié)點(diǎn)是鏈表前端結(jié)點(diǎn), 摘下摘下 else r-link = s-link;/排序碼最大結(jié)點(diǎn)是鏈表表中結(jié)點(diǎn)排序碼

9、最大結(jié)點(diǎn)是鏈表表中結(jié)點(diǎn), 摘下摘下 s-link = head-link; head-link = s;/結(jié)點(diǎn)結(jié)點(diǎn)s插入到結(jié)果鏈表的前端插入到結(jié)果鏈表的前端 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)542022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)550123450254312022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)560123450254312022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)57void FilterDown ( MaxHeap *H, int start, int EndOfHeap ) int i = start; int j = 2*i+1; HeadData t

10、emp = H-datai; while ( j = EndOfHeap ) /最后位置最后位置 if ( j dataj dataj+1 ) j = j+1; /選兩子女的大者選兩子女的大者 if ( temp = H-dataj ) break; else 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)58 H-datai = H-dataj; /大子女上移 i = j; j = 2*j+1; /向下繼續(xù)調(diào)整 H-datai = temp; /回放到合適位置2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)592022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)600123450254312022-

11、4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)610123450254312022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)620123450254312022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)630123450254312022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)640123450254312022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)652022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)662022kiiik1 12022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)67njnjjikkjkjjjkkjjkkii4 411111111202222222122)(2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)6

12、82022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)692022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)702022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)71 if ( InitListi = InitListj ) mergedList k = InitListi; i+; k+; else mergedList k = InitListj; j+; k+; 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)72 while ( i = mid ) mergedListk = InitListi; i+; k+; while ( j = right ) mergedListk = InitListj;

13、 j+; k+; 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)732022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)74void MergePass ( SortData initList , SortData mergedList , int len ) int i = 0; while (i+2*len-1 = n-1) merge( initList, mergedList, i, i+len-1, i+2*len-1); i += 2 * len; /循環(huán)兩兩歸并循環(huán)兩兩歸并 if ( i+len = n-1 ) ( initList, mergedList, i, i+len-1, n

14、-1); else for ( int j = i; j = n-1; j+) mergedList j = initListj; 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)752022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)762022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)772022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)7808 16temp = 722022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)79temp = 72temp = 7221 3725 372022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)80temp = 62temp = 6249 54結(jié)束2022-4-1北京化工大學(xué)信息學(xué)

15、院 數(shù)據(jù)結(jié)構(gòu)81typedef int SortData;void merge( SortData A , int left, int mid, int right ) int i, j; SortData temp; for ( i = left; i Amid+1 ) temp = Amid; for ( j = mid-1; j = i; j- ) Aj+1 = Aj; Ai = Amid+1; if ( temp = Amid+2 ) Amid+1 = temp; 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)82 else for ( j = mid+2; j Aj ) Aj-1 =

16、 Aj;else Aj-1 = temp; break; 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)83 比比較較次次數(shù)數(shù) 移移動(dòng)動(dòng)次次數(shù)數(shù)附附加加存存儲(chǔ)儲(chǔ)排排 序序 方方 法法最最好好最最差差最最好好最最差差穩(wěn)穩(wěn)定定 性性最最好好最最差差直直接接插插入入排排序序nn2 0n2 1折折半半插插入入排排序序n log2n 0n2 1起起泡泡排排序序nn2 0n2 1快快速速排排序序nlog2nn2n log2nn2 log2nn2簡(jiǎn)簡(jiǎn)單單選選擇擇排排序序n2 0n 1錦錦標(biāo)標(biāo)賽賽排排序序n log2nn log2n n堆堆排排序序n log2nn log2n 1歸歸并并排排序序n log2n

17、n log2n n2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)84242351179065485849255731建降序堆： 242351179065485849255731調(diào)整以65、90為根的子堆沒有變化，調(diào)整以17為根的子堆242351589065481749255731調(diào)整以51為根的子堆 242365589051481749255731調(diào)整以23為根的子堆 249065585751481749252331調(diào)整以24為根的子堆 905865495751481724252331建堆完畢!交換根與最后一片葉子，并摘除葉子 315865495751481724252390調(diào)整 655851

18、495731481724252390交換根與最后一片葉子，并摘除葉子 調(diào)整 235851495731481724256590585751492531481724236590交換根與最后一片葉子，并摘除葉子 調(diào)整 235751492531481724586590574951242531481723586590交換根與最后一片葉子，并摘除葉子 調(diào)整 234951242531481757586590514948242531231757586590交換根與最后一片葉子，并摘除葉子 調(diào)整 174948242531235157586590492548241731235157586590交換根與最后一片葉子

19、，并摘除葉子 調(diào)整 232548241731495157586590482531241723495157586590交換根與最后一片葉子，并摘除葉子 調(diào)整 232531241748495157586590312523241748495157586590交換根與最后一片葉子，并摘除葉子 調(diào)整 172523243148495157586590252423173148495157586590交換根與最后一片葉子，并摘除葉子 調(diào)整 172423253148495157586590241723253148495157586590交換根與最后一片葉子，并摘除葉子 調(diào)整 231724253148495157

20、586590172324253148495157586590排序完畢，得結(jié)果序列：17, 23, 24, 31, 48, 49, 51, 57, 58, 65, 90 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)98試題分析例例2. 已知待排序序列如下：已知待排序序列如下：14,12,16,1,4,7,3,8,10,15,2,5,13,9,11,6請(qǐng)寫出用快速排序法對(duì)其進(jìn)行升序排序的排序過程（依請(qǐng)寫出用快速排序法對(duì)其進(jìn)行升序排序的排序過程（依序?qū)懗雒恳惶藙澐值姆秶皠澐纸Y(jié)果，不必寫出劃分的序?qū)懗雒恳惶藙澐值姆秶皠澐纸Y(jié)果，不必寫出劃分的具體過程）。具體過程）。 2022-4-1北京化工大學(xué)信息學(xué)院 數(shù)據(jù)結(jié)構(gòu)99參考答案如下：參考答案如下：原