希尔排序.ppt

希尔排序 2 希尔排序是对直接插入排序算法的改进 其主要思想是 先将整个排序数列分割成为若干个子序列 在子序列分别进行直接插入排序 待整个数列基本有序时再对全部进行一次直接插入排序 以此来形成新的有序数列 一般分割方法是两个元素相距d n 2 n 4 n 8 以此类推 3 希尔 shell 排序 又称缩小增量排序 1 基本思想 把整个待排序的数据元素分成若干个小组 对同一小组内的数据元素用直接插入法排序 小组的个数逐次缩小 当完成了所有数据元素都在一个组内的排序后排序过程结束 2 技巧 小组的构成不是简单地 逐段分割 而是将相隔某个增量dk的记录组成一个小组 让增量dk逐趟缩短 例如依次取5 3 1 直到dk 1为止 3 优点 让关键字值小的元素能很快前移 且序列若基本有序时 再用直接插入排序处理 时间效率会高很多 4 38 例1 关键字序列T 49 38 65 97 76 13 27 49 55 04 请写出希尔排序的具体实现过程 初态 第1趟 dk 5 第2趟 dk 3 第3趟 dk 1 49 13 13 49 38 27 65 49 97 55 76 04 27 38 65 49 97 55 13 55 76 04 55 13 27 04 27 04 49 49 49 49 76 38 76 65 65 97 97 13 27 04 49 76 97 算法分析 开始时dk的值较大 子序列中的对象较少 排序速度较快 随着排序进展 dk值逐渐变小 子序列中对象个数逐渐变多 由于前面工作的基础 大多数对象已基本有序 所以排序速度仍然很快 可以看出 49 排序后出现在49的前面 故希尔算法是不稳定的 r i 5 原始序列 256 301 751 129 937 863 742 694 076 438 希尔排序 256 301 751 129 937 863 742 694 076 438 256 301 751 129 937 863 742 694 076 438 256 301 694 129 937 863 742 751 076 438 256 301 694 076 937 863 742 751 129 438 256 301 694 076 438 863 742 751 129 937 第1趟dk 5第2趟dk 3第3趟dk 1 256 301 694 076 438 863 742 751 129 937 256 301 694 076 438 863 742 751 129 937 076 301 694 256 438 863 742 751 129 937 076 301 694 256 438 863 742 751 129 937 076 301 694 256 438 863 742 751 129 937 076 301 129 256 438 694 742 751 863 937 076 301 129 256 438 694 742 751 863 937 076 301 129 256 438 694 742 751 863 937 076 129 256 301 438 694 742 751 863 937 例2 以关键字序列 256 301 751 129 937 863 742 694 076 438 为例 写出执行希尔排序 取dk 5 3 1 算法的各趟排序结束时 关键字序列的状态 希尔排序的算法templatevoiddataList ShellSort Elementtemp intgap CurrentSize 2 gap是子序列间隔while gap 0 循环 直到gap为零for inti gap i gap j gap if temp Vector j gap Vector j Vector j gap elsebreak Vector j temp gap int gap 2 Gap的取法有多种 最初shell提出取gap n 2 gap gap 2 直到gap 1 knuth提出取gap gap 3 1 还有人提出都取奇数为好 也有人提出