例如:将n个记录分成d个子序列 {R[0],R|d,R[2d RId j {R[l,R|1+d],R|1+2d,…,R[l+kdl} {R|d-1],R2d-1],R3d-1],…,RI(k+1)d-l} 其中,d称为增量,它的值在排序过程中从大到小逐 渐缩小,直至最后一趟排序减为1。 希尔排序也叫缩小增量排序. 16
16 其中，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] }
希尔排序示例 初始关键字序列:51336296871728515210 趟排序结果:17285152105133629687 二趟排序结果:17105133285152629687 趟排序结果:10172833515152628796 如何分组?意见不统一 shel:d1=Ln/2」,dn=d/2」 不稳定 17
17 希尔排序示例 二趟排序结果： 17 10 51 33 28 51 52 62 96 87 三趟排序结果： 10 17 28 33 51 51 52 62 87 96 初始关键字序列： 51 33 62 96 87 17 28 51 52 10 一趟排序结果： 17 28 51 52 10 51 33 62 96 87 如何分组？意见不统一 Shell： d n / 2 ,d d / 2 1 i 1 i = = + 不稳定
例10.2设待排序的表有10个记录,其关键字分别为 {9,8,7,6,5,4,3,2,1,0}。说明采用希尔排序方法进行排序的过程 初始状态 876 0(连线部分为下一趟作准备) d=5 432 098765(d=5执行结果) d=2 456789(d=2执行结果) 0 23456789(d=1执行结果)
18 例 10.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 执行结果)
void she1sort( RecType R],intn)/希尔排序算法 I int l,j, gap; RecType tmpi gap=n/2; //d取初值n/2 while(gap>0) ￡ox(i=gap;i<n;i++)//将R[d.n-1]分别插入各组当前有序区 t tmp=R[i]i 丁=1-gap; while (3>=0 & tmp key<R[j].key) R[]+gap]= R[JI; 丁--gap; R[]+gap]=tmpi gap=gap/2; //递减增量d
19 void ShellSort(RecType R[],int n) //希尔排序算法 { int i,j,gap; RecType tmp; gap=n/2; //d取初值n/2 while(gap>0) { for(i=gap;i<n;i++) //将R[d..n-1]分别插入各组当前有序区 { tmp=R[i]; j=i-gap; while (j>=0 && tmp.key<R[j].key) { R[j+gap]= R[j]; j=j-gap; } R[j+gap]=tmp; } gap=gap/2; //递减增量d } }
103交换排序 交换排序的基本思想 两两比较待排序记录的关键字,发现两个记录 的次序相反时即进行交换,直到没有反序的记 录为止 通过交换记录的位置达到排序的目的 两种交换排序: (1)冒泡排序 (2)快速排序
20 • 交换排序的基本思想： •两两比较待排序记录的关键字，发现两个记录 的次序相反时即进行交换，直到没有反序的记 录为止。 •通过交换记录的位置达到排序的目的 • 两种交换排序: (1)冒泡排序 (2)快速排序 10.3 交换排序