数据结构与算法设计PPT (44).pdf

第9章 排序9.3 希尔排序2021/2/241 直接插入排序的效率较低-移动数据元素和交换数据元素的次数都是O(n2)以下情形效率较高-待排序数据元素基本有序-序列中的数据元素个数较少时 希尔排序就是利用这两个特点进行的改近直接插入排序的性能分析希尔排序(Shell Sort)希尔排序方法又称为缩小增量排序。该方法的基本思想是-设待排序对象序列有n 个对象，首先取一个整数gap n 作为间隔，将全部对象分为gap 个子序列，所有距离为gap 的对象放在同一个子序列中-在每一个子序列中分别进行直接插入排序。-然后缩小间隔gap，例如取gap=gap/2-重复上述的子序列划分和排序工作。直到最后取gap=1，将所有对象放在同一个序列中排序为止。21254925*16080 1 2 3 4 52125*i=10849Gap=32516492516084925*0821252125*1621254925*16080 1 2 3 4 521i=20849Gap=22516491625*0821254925*08162125*2521254925*16080 1 2 3 4 521i=308Gap=125164925*开始时gap 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，gap值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。希尔排序不是稳定的排序算法希尔排序算法的特点template void Shellsort(datalist&list)intgap=list.CurrentSize/2;/gap 是子序列间隔while(gap)/循环,直到gap为零ShellInsert(list,gap);/一趟直接插入排序gep=gep=2?1:(int)(gap/2.2);/修改希尔排序算法的实现template voidshellInsert(datalist&list;const intgep)/一趟希尔排序,按间隔gap划分子序列for(inti=gap;i list.CurrentSize;i+)Elementtemp=list.Vectori;int j=i;while(j=gap&temp.getKey()list.Vectorj-gap.getKey()list.Vectorj=list.Vectorj-gap;j-=gap;list.Vectorj=temp;希尔排序算法的实现算法分析 对特定的待排序对象序列，可以准确地估算关键码的比较次数和对象移动次数。Knuth利用大量的实验统计资料得出，当 n 很大时，关键码平均比较次数和对象平均移动次数大约在n1.25到 1.6n1.25的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。