Chap8_算法與數(shù)據(jù)結(jié)構(gòu)—C語言描述(第2版

1、1整理ppt2整理ppt 在待排序的文件中，如果存在多個排序碼相同的記在待排序的文件中，如果存在多個排序碼相同的記錄，經(jīng)過排序后，相同排序碼記錄的相對次序如果保持錄，經(jīng)過排序后，相同排序碼記錄的相對次序如果保持不變，則稱這種排序方法是穩(wěn)定的，否則是不穩(wěn)定的。不變，則稱這種排序方法是穩(wěn)定的，否則是不穩(wěn)定的。3整理ppt4整理ppt例例49 38 65 97 76 13 27 49i=1 38 (38 49) 65 97 76 13 27 49i=2 65 (38 49 65) 97 76 13 27 49i=3 97 (38 49 65 97) 76 13 27 49i=4 76 (38 49

2、65 76 97) 13 27 49i=5 13 (13 38 49 65 76 97) 27 49 ( )i=6 (13 38 49 65 76 97) 27 4927jjjjjj97)7665493827 (13 27 38 49 65 76 97)排序結(jié)果：排序結(jié)果：i=7 49 (13 38 49 49 65 76 97) 27 5整理ppt42n42nT(n)=O(n)6整理ppt例例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20.i=8 20 (6

3、13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sji=8 20 (6 13 20 30 39 42 70 85 )7整理ppt8整理ppt取d3=1三趟分組：13 27 48 55 4 49 38 65 97 76三趟排序：4 13 27 38 48 49 55 65 76 97例 初始： 49 38 65 97 76 13 27 48 55 4一趟排序：13 27 48 55 4 49

4、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 76v算法描述例49 38 65 97 76 13 27 48 55 4#define T 3int d=5,3,1;ji49133827一趟排序：13 27 48 55 4 49 38 65 97 76jiji274jiji55ji38jijiji二趟排序：13 4 48 38 27 49 55 65 97 76jiji6548ji9755ji76411整理p

5、pt12整理ppt例初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 排序結(jié)束： 13 27 38 49 65 76 9714整理pptT(n)=O(n)15整理ppt或(i=0,1,.n/2-1)kik2i+1kik2i+2kik2i+1

6、kik2i+2例 （96，83，27，38，11，9） 例 （13，38，27，50，76，65，49，97）962791138831327384965765097可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中n個元素的最小值或最大值16整理ppt17整理ppt例13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13 273849502765769713輸出：13 276549502738769713輸出：13 27 3818整理ppt4965502738769713輸出：

7、13 27 387665502738499713輸出：13 27 38 495065762738499713輸出：13 27 38 499765762738495013輸出：13 27 38 49 506597762738495013輸出：13 27 38 49 509765762738495013輸出：13 27 38 49 50 6519整理ppt7665972738495013輸出：13 27 38 49 50 659765762738495013輸出：13 27 38 49 50 65 769765762738495013輸出：13 27 38 49 50 65 76 9720整理pp

8、t21整理ppt例 含8個元素的無序序列（49，38，65，97，76，13，27，50）4965382713769750496538271376509749133827657650974913382765765097132738496576509722整理ppt23整理ppt例49 38 65 97 76 13 27 30 初始關(guān)鍵字38 49 65 76 13 27 30 97 第一趟38 49 65 13 27 30 76 第二趟38 49 13 27 30 65 第三趟38 13 27 30 49 第四趟13 27 30 38 第五趟13 27 30 第六趟38497697139727

9、97309713767676273013652765306513134949304927382738303825整理pptT(n)=O(n)26整理ppt例初始關(guān)鍵字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij28整理pptT(n)=O(n)29整理ppt例例 對對52張撲克牌按以下次序排序：張撲克牌

10、按以下次序排序： 2 3 A 2 3 A 2 3 A 2 3 A兩個關(guān)鍵字：花色（兩個關(guān)鍵字：花色（ ） 面值（面值（23A）并且并且“花色花色”地位高于地位高于“面值面值”30整理ppt31整理ppt32整理ppt例初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：33整理ppt505008109930063269278083184589二趟收集：二趟收集：

11、083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配二趟分配008109278930063083184505278008109589269一趟收集：一趟收集：34整理ppt008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配三趟分配063083269278505589505008109930063269278083184589二趟收集：二趟收集：35整理ppt36整理ppt37整理ppt例例初始關(guān)鍵字