

希尔排序

Shell 排序是以它的发明者命名的，也称为缩小增量排序法。Shell 排序对不相邻的记录进行比较和移动：

1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）
2. 对这些子序列进行插入排序
3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1

Shell 排序的复杂度和间距序列的选取（就是间距如何减小到 1）有关，比如“间距每次除以 3”的 Shell 排序的复杂度是 $O(n^{3/2})$ 。

---

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论