将记录序列分成若干子序列,分别对每个子序列进行插入排序 例如:将n个记录分成d个子序列: {R|0,Rd,R2d,∴,R[kd} {R[l,R[1+l,R[1+2a,…,R[1l+kl} {R[d-1,R2d-1,R|3d-1,…,R[(k+1)d-1} 其中,d称为增量,它的值在排序过程中从大到小逐渐缩小 直至最后一趟排序减为1
将记录序列分成若干子序列，分别对每个子序列进行插入排序。 其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小， 直至最后一趟排序减为 1。 例如：将 n 个记录分成 d 个子序列： { R[0]， R[d]， R[2d]，…， R[kd] } { R[1]， R[1+d]， R[1+2d]，…，R[1+kd] } … { R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1] }
例如: 162512304711233691831 设增量d=5 112312918162536304731
例如： 16 25 12 30 47 11 23 36 9 18 31 设增量 d =5: 11 23 12 9 18 16 25 36 30 47 31
public void Shellsort0/对R10.n-1按递增有序进行希尔排序 int i,j, d; RecType tmp; d=length/2 /增量置初值 while(d>o) {for(i=d; i<length;i++)/对所有相隔d位置的元素组采用直接插入排序 tmp=Ri d while(j>=0&&tmp.key<Rj]key)/对相隔d位置的元素组进行排序 t RIj+d=rll; j=j-d: RI+d=tmp; d=d/2 /减咸小增量
public void ShellSort() //对R[0..n-1]按递增有序进行希尔排序 { int i,j,d; RecType tmp; d=length/2; //增量置初值 while (d>0) { for (i=d;i<length;i++) //对所有相隔d位置的元素组采用直接插入排序 { tmp=R[i]; j=i-d; while (j>=0 && tmp.key<R[j].key)//对相隔d位置的元素组进行排序 { R[j+d]=R[j]; j=j-d; } R[j+d]=tmp; } d=d/2; //减小增量 } }
例92设待排序的表有10个记录,其关键字分别为 {9,8,7,6,5,4,3,2,1,0}。说明采用希尔排序方法进行排序的过程。 初始状态98 0(连线部分为下一趟作准备) d=5 098765(d=5执行结果) d=2 23456789(d=2执行结果) 0 23456789(d=1执行结果)
例 9.2 设 待 排 序 的 表 有 10 个记录 , 其 关 键 字 分 别 为 {9,8,7,6,5,4,3,2,1,0}。说明采用希尔排序方法进行排序的过程。 初始状态 9 8 7 6 5 4 3 2 1 0 (连线部分为下一趟作准备) d=5 4 3 2 1 0 9 8 7 6 5 (d=5 执行结果) d=2 0 1 2 3 4 5 6 7 8 9 (d=2 执行结果) d=1 0 1 2 3 4 5 6 7 8 9 (d=1 执行结果)
希尔排序的时间复杂度约为O(n13) 为什么希尔排序比直接插入排序好? 例如:有10个元素要排序 希尔排序 直接插入排序 d=5:分为5组,时间约为5*22=20 大约时间=102=100 d=2:分为2组,时间约为2*52=50 d=1:分为1组,几乎有序,时间约为10 80
希尔排序的时间复杂度约为O(n1.3)。 为什么希尔排序比直接插入排序好？ 例如：有10个元素要排序。 希尔排序 直接插入排序 大约时间=102=100 d=5：分为5组，时间约为5*22＝20 d=2：分为2组，时间约为2*52＝50 d=1：分为1组，几乎有序，时间约为10 ＋ ＋ ＝80