【8.2】内排序--插入排序 ( Shell 排序)

一、直接插入排序

算法分析：

• 稳定
• 空间代价:Θ(1)
• 时间代价:

二、Shell 排序

• 直接插入排序的两个性质:
• 在最好情况(序列本身已是有序的)下时间代价为 Θ(n)
• 对于短序列，直接插入排序比较有效
• Shell 排序有效地利用了直接插入排序的 这两个性质

Shell排序算法思想：

• 先将序列转化为若干小序列，在这些小序列内 进行插入排序
• 逐渐增加小序列的规模，而减少小序列个数， 使得待排序序列逐渐处于更有序的状态
• 最后对整个序列进行扫尾直接插入排序，从而 完成排序

“增量每次除以2递减”的Shell 排序：

针对增量而修改的插入排序算法：

算法分析：

• 不稳定
• 空间代价:Θ(1)
• 时间代价
• 增量每次除以2递减，Θ(n2)
• 选择适当的增量序列
• 可以使得时间代价接近 Θ(n)

Shell 排序选择增量序列：

Hibbard 增量序列

• Hibbard 增量序列
• {2^k -1，2^(k-1)-1，…，7，3，1}
• Shell(3) 和 Hibbard 增量序列的 Shell 排序的效率可以达到 Θ(n^3/2)
• 选取其他增量序列还可以更进一步减 少时间代价

Shell最好的代价:

• 呈 2^p3^q 形式的一系列整数: 1,2,3,4,6,8,9,12
• Θ(n log2n)

三、思考

1. 插入排序的变种

• 发现逆序对直接交换
• 查找待插入位置时，采用二分法

2. Shell 排序中增量作用是什么?增量为2和增量 为3的序列，哪个更好?为什么?

3. Shell 排序的每一轮子序列排序 可以用其他方法吗?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾