Chap8_算法与数据结构—C语言描述(第2版

1、1整理ppt2整理ppt 在待排序的文件中，如果存在多个排序码相同的记在待排序的文件中，如果存在多个排序码相同的记录，经过排序后，相同排序码记录的相对次序如果保持录，经过排序后，相同排序码记录的相对次序如果保持不变，则称这种排序方法是稳定的，否则是不稳定的。不变，则称这种排序方法是稳定的，否则是不稳定的。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)排序结果：排序结果：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 排序结束： 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 初始关键字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例初始关键字： 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) 快速排序结束： 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两个关键字：花色（两个关键字：花色（ ） 面值（面值（23A）并且并且“花色花色”地位高于地位高于“面值面值”30整理ppt31整理ppt32整理ppt例初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：33整理ppt505008109930063269278083184589二趟收集：二趟收集：

11、083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配二趟分配008109278930063083184505278008109589269一趟收集：一趟收集：34整理ppt008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配三趟分配063083269278505589505008109930063269278083184589二趟收集：二趟收集：35整理ppt36整理ppt37整理ppt例例初始关键字