令希尔排疡缩小增量排房 基本想:对待排记录序列先作“宏观”调整, 再作“微观”调整 所谓“宏观”调整,指的是“跳跃式”的插入排 序。具体做法为: 将记录序列分成若干个子序列,分别对每个 子序列进行插入排序 例如,将n个记录分为d个子序列: {R[1,R[1+d],R[1+2dl,…R[l+kd {R[2|,R2+d]R2+2dl,R[2+kd Rdr2dlr dbo. RI(+kd 1其中,(称为增量,它的值在排璃过程中从大到小
11 ❖希尔排序(缩小增量排序) 基本思想：对待排记录序列先作“宏观”调整， 再作“微观”调整。 所谓“宏观”调整，指的是“跳跃式”的插入排 序。具体做法为： 将记录序列分成若干个子序列，分别对每个 子序列进行插入排序 其中，d称为增量，它的值在排序过程中从大到小 逐渐缩小，直至最后一趟排序减为1。 {R[1],R[1+d],R[1+2d],…,R[1+kd]} {R[2],R[2+d],R[2+2d],…,R[2+kd]} … {R[d],R[2d],R[3d],…,R[(1+k)d]} 例如，将n个记录分为d个子序列:
例始状态:4386597761327495549 趟分组:43865977613274955 取d1=5 趟排序:4274955491338659776 二趟分组:4274955491338659776 取d2=2 二趟排序:4133827495549659776 hellsort 取d3=1 三趟分组:4133827495549659776 三趟排序:4132738494955657697
取d3=1 三趟分组：4 13 38 27 49’ 55 49 65 97 76 三趟排序：4 13 27 38 49’ 49 55 65 76 97 例:初始状态：4 38 65 97 76 13 27 49’ 55 49 一趟排序：4 27 49’ 55 49 13 38 65 97 76 二趟排序：4 13 38 27 49’ 55 49 65 97 76 一趟分组：4 38 65 97 76 13 27 49’ 55 49 取d1=5 二趟分组： 取d2=2 4 27 49’ 55 49 13 38 65 97 76
◇希尔推序指点 子序列的构成不是简单的“逐段分割 而是将相隔某个增量的记录组成一个子序 列 >希尔排序可提高排序速度,因为 分组后n值减小,n2更小,而T(m)=O(m2) 所以T(m)从总体上来说是减小了 关键字较小的记录跳跃式前移,在进行 最后一趟增量为1的插入排序时,序列己 基本有序 >增量序列取法 无除1以外的公因子 》最后一个增量值必须为1 13>希尔排序是不稳定的如(5,2,2)
13 ❖希尔排序特点 ➢子序列的构成不是简单的“逐段分割”， 而是将相隔某个增量的记录组成一个子序 列 ➢希尔排序可提高排序速度，因为 »分组后n值减小，n²更小，而T(n)=O(n²), 所以T(n)从总体上来说是减小了 »关键字较小的记录跳跃式前移，在进行 最后一趟增量为1的插入排序时，序列已 基本有序 ➢增量序列取法 »无除1以外的公因子 »最后一个增量值必须为1 ➢希尔排序是不稳定的如（5，2，2）
113交换排序 交换推序的基本思想:两两比较待排序记录的关键 字,发现两个记录的次序相反时即进行交换,直到没 有反序的纪录为止。1.冒泡排序2.快速推序字 1.泡房 假设在排序过程中,记录序列R0n-1的状态为 有序序列R0.无序序列Rn11 第趟起泡排序 比较死,将 关键字蛋最小的记录 交英缈的位置上 14 有序序列R[0.无序序列RH+1,n-1
14 11.3 交换排序 交换排序的基本思想：两两比较待排序记录的关键 字，发现两个记录的次序相反时即进行交换，直到没 有反序的纪录为止。1. 冒泡排序 2. 快速排序 1. 冒泡排序 假设在排序过程中，记录序列R[0..n-1]的状态为： 有序序列R[0..i-1] 无序序列R[i,..n-1] i-1 第i趟起泡排序 比较相邻记录，将 关键字最小的记录 交换到i的位置上 有 序 序 列 R[0..i]无序序列R[i+1,..n-1]
void Bubble Sort(RecType Rll, int n) i int i,j; RecType temp; a 6 for(=0;i<n1:计+)=0=1F2i=3i=45结束 for〔=n-1>i:j-)j5~1j5~2j5~3 if(|key<R1key)j从5~4j取5 i temp=Riil RIlRIj-1; 初始关鍵字a Ri-1-temp; 0 1 2 345 5812172336 由该例我们看出第3趟排序时,该序列就已经 15 排好了,但仍执行第4、第5趟排序
15 void BubbleSort(RecType R[], int n) { int i,j；RecType temp; for (i=0;i<n-1;i++) { for (j=n-1;j>i;j--) if (R[j].key<R[j-1].key) { temp=R[j]; R[j]=R[j-1]; R[j-1]=temp; } } } 5 12 23 36 17 8 初始关键字a[] a 6 i=0 j从5～1 0 1 2 3 4 5 5 88 128 238 368 17 i=1 j从5～2 8 17 23 17 36 i=2 j从5～3 i=3 j从5～4 i=4 j取5 i=5 结束 由该例我们看出第3趟排序时，该序列就已经 排好了，但仍执行第4、第5趟排序