1、算法思想
希尔(Shell)排序又称为缩小增量排序,它是一种插入排序。它是直接插入排序算法的一种威力加强版。
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
如下图所示为算法模拟过程:
2、代码
1 |
|
3、算法分析
3-1、性能分析
3-2、直接插入排序与希尔排序的比较
直接插入排序是稳定的;而希尔排序是不稳定的。
直接插入排序更适合于原始记录基本有序的集合。
希尔排序的比较次数和移动次数都要比直接插入排序少,当N越大时,效果越明显。
希尔排序的比较次数和移动次数都要比直接插入排序少,当N越大时,效果越明显。
直接插入排序也适用于链式存储结构;希尔排序不适用于链式结构。