《Chap8_算法与数据结构—C语言描述(第2版)张乃孝编课件》由会员分享，可在线阅读，更多相关《Chap8_算法与数据结构—C语言描述(第2版)张乃孝编课件（38页珍藏版）》请在装配图网上搜索。
1、 在待排序的文件中，如果存在多个排序码相同的记录，经过排序后，相同排序码记录的相对次序如果保持不变，则称这种排序方法是稳定的，否则是不稳定的。 例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 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 4927 jj j jjj
2、 9 )7665493827 (13 27 38 49 65 76 97)排序结果：i=7 49 (13 38 49 49 65 76 97) 27 42n42n T(n)=O (n) 例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 13 30 39 42 70 85 ) 20s jmi=8 20 (6 13 30 39 42 70 85 ) 20s jmi=8 20 (6 13 30 39 42 70 85 ) 20s jmi=8 20
3、(6 13 30 39 42 70 85 ) 20sji=8 20 (6 13 20 30 39 42 70 85 ) 取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 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
4、 97 76 v算 法 描 述例49 38 65 97 76 13 27 48 55 4#define T 3int d=5,3,1;j i4913 3827一趟排序：13 27 48 55 4 49 38 65 97 76j ij i274 j ij i55j i38 j ij ij i 二趟排序：13 4 48 38 27 49 55 65 97 76j ij i6548 j i9755 j i764 例初始： 49 38 65 97 76 13 27 k j j j j j jk ki=1 13 49一趟： 13 38 65 97 76 49 27 i=2 k kj j j jj27 3
5、8二趟： 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 97 T(n)=O (n) 或(i=0,1,.n/2-1)kik2i+1kik2i+2 kik2i+1kik2i+2例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）96 279113883 13 2738 4965765097可将堆序列看成完全二叉树，则
6、堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值 例13 2738 4965765097 97 2738 4965765013输出：13 27 4938 9765765013输出：1397 4938 27657650 13输出：13 27 38 4950 2765769713输出：13 27 65 4950 2738769713输出：13 27 38 49 6550 2738769713输出：13 27 38 76 6550 2738499713输出：13 27 38 49 50 6576 2738499713输出：13 27 38 4997 6576 27384950 13输出：
7、13 27 38 49 50 65 9776 2738495013输出：13 27 38 49 50 97 6576 2738495013输出：13 27 38 49 50 65 76 6597 2738495013输出：13 27 38 49 50 65 97 6576 2738495013输出：13 27 38 49 50 65 7697 6576 2738495013 输出：13 27 38 49 50 65 76 97 例 含8个元素的无序序列（49，38，65，97，76，13，27，50）49 6538 2713769750 49 6538 2713765097 49 1338 2
8、76576509749 1338 27657650 97 13 2738 4965765097 例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 第六 趟38497697139727973097 137676762730 136527653065 13 134949304927 382738038 T(n)=O (n) 例初始关键字：
9、49 38 65 97 76 13 27 50 i jx ji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 974927 i i ji j49 65j13 49i49 97ij T(n)=O (n) 例 对52张扑克牌按以下次序排序：23A23A23A23A两个关键字：花色（ ） 面值（23A）并且“花色”地位高于“面值” 例初始状态：278 109 063 930 589 184 505 269 008 08310958
10、9269278063930 083 184 505 008e0 e1 e2 e3 e4 e5 e6 e7 e8 e9f0 f1 f2 f3 f4 f5 f6 f7 f8 f9一趟分配 930 063 083 184 505 278 008 109 589 269一趟收集： 505 008 109 930 063 269 278 083 184 589二趟收集：083184589063505 269930e0 e1 e2 e3 e4 e5 e6 e7 e8 e9f0 f1 f2 f3 f4 f5 f6 f7 f8 f9二趟分配008109 278 930 063 083 184 505 278
11、008 109 589 269一趟收集： 008 063 083 109 184 269 278 505 589 930三趟收集：109008 184 930e0 e1 e2 e3 e4 e5 e6 e7 e8 e9f0 f1 f2 f3 f4 f5 f6 f7 f8 f9三趟分配063083 269278 505589 505 008 109 930 063 269 278 083 184 589二趟收集： 例初始关键字： 49 38 65 97 76 13 27一趟归并后： 38 49 65 97 13 76 27二趟归并后： 38 49 65 97 13 27 76三趟归并后： 13 27 38 49 65 76 97
Chap8_算法与数据结构—C语言描述(第2版)张乃孝编课件
