§10.2.1直接插入排序（续） §10.2.2希尔排序 ◆移动：内循环中R[1.11]均后移，外加设置哨 兵和将R[叮插到最终位置共移动i-1+2=+1. 希尔排序(Shell Sort,又称缩小增量法)是一种分 M=之+=0 组插入排序方法。 1排序思想 ③平均： 若记录随机分布。比较、移动平均为n214 ①先取一个正整数d(d<n)作为第一个增量，将全 部n个记录分成d,组，把所有相隔d,的记录放在一组 中，即对于每个k(k=1,2,.d),Rk],Rd+k R2d+k],分在同一组中，在各组内进行直接插入 排序。这样一次分组和排序过程称为一趟希尔排序： ②取新的增量d2<d1,重复①的分组和排序操作： 直至所取的增量d,=1为止，即所有记录放进一个组中 排序为止。 2排序示例 3 算法实现 设有10个待排序的记录，关键字分别为9,13,8,2 先给出一越希尔排序的算法，类似直接插入排序。 5,13,7,1,15.11,增量序列是5,3,1，希尔排序的过 void shell_pass(Sqlist *L int d) 程如图所示。 :对顺序表L进行一趟希尔排序，增量为d 初始关键字序列：9138253 711511 int i.k; 3 for (j=d+1;j<=L->length;j++) 第一热排序过程： L->R[0=L->R[jl; 产设置监视哨兵*/ k=j-d; while(k>0&&LT(L->R[0J.key,L->R[k].key)) L->R[k+d]=L->R[k]k=k-d;} 第二排序后：2519713118153 L->R[k+jl=L->R[0]; 第三趙排序后：125789111313 15 希尔排序过程 然后在根据增量数组dk进行希尔排序。 希尔排序可提高排序速度，原因是： void shell sort(Sqlist *L,int dk[,int t) ◆分组后n值减小，更小，而T(n=0,所以T(o) :按增量序列k0..t-1,对顺序表L进行希尔排序*/ 从总体上看是减小了： intm; ◆关键字较小的记录跳跃式前移，在进行最后一越 for (m=0;m<=t;m++) 增量为1的插入排序时，序列已基本有序。 shll pass(L,dk m]); ◆当n较大时，比较和移动次数约在n25 1.6n125之间 希尔排序的分析比较复杂，涉及一些数学上的问 增量序列取法 题，其时间是所取的“增量”序列的函数。 ◆无除1以外的公因子： 希尔排序特点 ◆最后一个增量值必须为1。 子序列的构成不是简单的“逐段分割”，而是将相隔 某个增量的记录组成一个子序列。7 §10.2.1 直接插入排序（续） ‹ 移动：内循环中R[1..i-1]均后移，外加设置哨 兵和将R[i]插到最终位置共移动i-1+2=i+1. ③ 平均： 若记录随机分布。比较、移动平均为n2/4 2 max 2 ( 1) ( ) n i M i On = = += ∑ §10.2.2 希尔排序 希尔排序(Shell Sort，又称缩小增量法)是一种分 组插入排序方法。 1 排序思想 ① 先取一个正整数d1(d1<n)作为第一个增量，将全 部n个记录分成d1组，把所有相隔d1的记录放在一组 中，即对于每个k(k=1, 2, … d1)，R[k], R[d1+k], R[2d1+k] , …分在同一组中，在各组内进行直接插入 排序。这样一次分组和排序过程称为一趟希尔排序； ② 取新的增量d2<d1，重复①的分组和排序操作； 直至所取的增量di =1为止，即所有记录放进一个组中 排序为止。 2 排序示例 设有10个待排序的记录，关键字分别为9, 13, 8, 2, 5, 13, 7, 1, 15, 11，增量序列是5, 3, 1，希尔排序的过 程如图所示。 第一趟排序后: 9 7 1 2 5 13 13 8 15 11 第二趟排序后: 2 5 1 9 7 13 11 8 15 13 第三趟排序后: 1 2 5 7 8 9 11 13 13 15 希尔排序过程 9 13 8 2 5 13 7 1 15 11 7 13 1 8 初始关键字序列: 第一趟排序过程: 3 算法实现 先给出一趟希尔排序的算法，类似直接插入排序。 void shell_pass(Sqlist *L, int d) /* 对顺序表L进行一趟希尔排序, 增量为d */ { int j, k ; for (j=d+1; j<=L->length; j++) { L->R[0]=L->R[j] ; /* 设置监视哨兵 */ k=j-d ; while (k>0&&LT(L->R[0].key, L->R[k].key) ) { L->R[k+d]=L->R[k] ; k=k-d ; } L->R[k+j]=L->R[0] ; } } 然后在根据增量数组dk进行希尔排序。 void shell_sort(Sqlist *L, int dk[], int t) /* 按增量序列dk[0 … t-1],对顺序表L进行希尔排序 */ { int m ; for (m=0; m<=t; m++) shll_pass(L, dk[m]) ; } 希尔排序的分析比较复杂，涉及一些数学上的问 题，其时间是所取的“增量”序列的函数。 希尔排序特点 子序列的构成不是简单的“逐段分割”，而是将相隔 某个增量的记录组成一个子序列。 希尔排序可提高排序速度，原因是： ◆ 分组后n值减小，n²更小，而T(n)=O(n²),所以T(n) 从总体上看是减小了； ◆ 关键字较小的记录跳跃式前移，在进行最后一趟 增量为1的插入排序时，序列已基本有序。 ◆ 当n较大时，比较和移动次数约在n1.25~ 1.6n1.25之间 增量序列取法 ◆ 无除1以外的公因子； ◆ 最后一个增量值必须为1