今希尔排序特点 ●子序列的构成不是简单的“逐段分割”,而是将相隔某个增 量的记录组成一个子序列 ●希尔排序可提高排序速度,因为 ◆分组后n值减小,n更小,而T(n)=O(n2),所以T(n)从总体 上看是减小了 ◆关键字较小的记录跳跃式前移,在进行最后一趟增量为1 的插入排序时,序列己基本有序 ●增量序列取法 ◆无除1以外的公因子 ◆最后一个增量值必须为1
❖希尔排序特点 ⚫子序列的构成不是简单的“逐段分割”，而是将相隔某个增 量的记录组成一个子序列 ⚫希尔排序可提高排序速度，因为 ◆分组后n值减小，n²更小，而T(n)=O(n²),所以T(n)从总体 上看是减小了 ◆关键字较小的记录跳跃式前移，在进行最后一趟增量为1 的插入排序时，序列已基本有序 ⚫增量序列取法 ◆无除1以外的公因子 ◆最后一个增量值必须为1
§8.2交换排序 ★冒泡排序 今排序过程 将第一个记录的关键字与第二个记录的关键字进行比较,若 为逆序[1key>[2]key,则交换;然后比较第二个记录与第 个记录;依次类推,直至第n1个记录和第n个记录比较为 止——第一趟冒泡排序,结果关键字最大的记录被安置在最 后一个记录上 ●对前η-1个记录进行第二趟冒泡排序,结果使关键字次大的记 录被安置在第n∩-1个记录位置 ●重复上述过程,直到“在一趟排序过程中没有进行过交换记 录的操作”为止
§8.2 交换排序 冒泡排序 ❖排序过程 ⚫将第一个记录的关键字与第二个记录的关键字进行比较，若 为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第 三个记录；依次类推，直至第n-1个记录和第n个记录比较为 止——第一趟冒泡排序，结果关键字最大的记录被安置在最 后一个记录上 ⚫对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记 录被安置在第n-1个记录位置 ⚫重复上述过程，直到“在一趟排序过程中没有进行过交换记 录的操作”为止
例38383838131313 49494913272727 6565 2730 3030 76 132730 38 38 13 273049 49 U 30 27 3065 3065 3076 3076 97 第第第第 初始关键字 儿u 第五趟一 第六趟
例 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第六趟 38 49 76 9713 972 9730 97 13 76 76 7627 30 13 6527 6530 65 13 13 49 4930 4927 3827 380 38
今算法描述 Ch8 txt 今算法评价 ●时间复杂度 ◆最好情况(正序) 比较次数:n-1 移动次数:0 ◆最坏情况(逆序) 比较次数:(n-)=1(m2-n) 移动次数:3(n-0)=3(m2-n) T(n)=O(n2) ●空间复杂度:S(n)=O(1) Ch8 4.c
❖算法描述 ❖算法评价 ⚫时间复杂度 ◆最好情况（正序） 比较次数：n-1 移动次数：0 ◆最坏情况（逆序） 比较次数： ( ) 2 1 ( ) 2 1 1 n i n n n i − = − − = 移动次数： ( ) 2 3 3 ( ) 2 1 n i n n n i − = − = ⚫空间复杂度：S(n)=O(1) T(n)=O(n²) Ch8_4.c