希尔排序1.ppt

希尔排序
汇报人:王曦
组员:马志豪、孙天洋、王明远、刘讯。
基本思想
方法与过程
C++代码实现
练****br/>目录
希尔排序
希尔排序
基本思想:
希尔排序属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。先取一个小于n的整数h1作为第一个增量,把文件的全部记录分成h1个组。所有距离为h1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量h2<h1重复上述的分组和排序,直至所取的增量ht=1(ht<ht-l<…<h2<h1),即所有记录放在同一组中进行直接插入排序为止。
基本思想
方法与过程
子序列分割方法:
,分别进行
插入排序。在排序的过程中逐次减小这个增量,
最后当h=1时,进行一次插入排序,排序完成。
=n/2^k(k=1,2,…/[㏒ 2^n]),其中n为待排序列的长度。
希尔排序
方法与过程
希尔排序
<n,把所有序号相隔h1的数组元素放一组,组内进行直接插入排序。
排序过程:
07
19
24
13
31
08
82
18
44
63
05
29
h=6
方法和过程
希尔排序
第一子序列:
第三子序列:
第二子序列:
第六子序列:
第四子序列:
第五子序列:
第一次排序结果:
07
82
18
19
24
44
13
63
05
31
08
29
07 18 24 13 05 08 82 19 44 63 31 29
方法与过程
07
18
24
13
05
08
82
19
44
63
31
29
<h1,重复上述分组和排序操作;直至ht=1,即所有记录放进一个组中排序为止。
h=3
第一子序列:07 13 63 82
第二子序列:05 18 19 31
第三子序列:08 24 29 44
第二次排序结果:
07 05 08 13 18 24 63 19 29 82 31 44
希尔排序
07
05
24
13
31
08
82
18
44
63
05
29
h=1
第三次排序:
第三次排序结果:
05 07 08 13 18 19 24 29 31 44 63 82
希尔排序
方法与过程
最终排序结果:
05 07 08 13 18 19 24 29 31 44 63 82
希尔排序
方法与过程
增量序列取法:
没有除1以外的公因子,最后一个增量值必须为1。
T(n) = O(n )
希尔排序的时间是所取“增量”序列的函数。
希尔排序
时间分析