## 希尔排序 ### 简介 希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 ### 工作原理 排序对不相邻的记录进行比较和移动： 1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）； 2. 对这些子序列进行插入排序； 3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。 ### 演示  也可以在[这个网站](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)选择Sheel sort自己测试。 ### 步长序列 步长的选择是希尔排序的重要部分。不同的步长时间会有所不同。 我们一般会选择每次步长除以$2$或$3$。 ### 性质 希尔排序是一种不稳定的排序，希尔排序的最优时间复杂度为 $O(n\log n)$，当 步长每次除以 $3$ 时，时间复杂度为 $O(n^{\frac{3}{2}})$。当前最好的步长选择的最坏时间复杂度为 $O(n\log^2 n)$，空间复杂度为 $O(n)$。 ### 实现 代码可以在这里测试：[Luogu P1177 【模板】快速排序](https://www.luogu.com.cn/problem/P1177) 步长每次除以 $3$，数组下标从 $1$ 开始代码： ```c++ int h=1; while (h<n/3) h=h*3+1; while (h) { for (int i=h+1; i<=n; i++) for (int j=i; j>h && a[j]<a[j-h]; j-=h) swap(a[j], a[j-h]); h/=3; } ``` ## 参考 1. [维基百科](https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F) 2. [OI-Wiki](https://oi-wiki.org/basic/shell-sort/) Loading... ## 希尔排序 ### 简介 希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 ### 工作原理 排序对不相邻的记录进行比较和移动： 1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）； 2. 对这些子序列进行插入排序； 3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。 ### 演示  也可以在[这个网站](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)选择Sheel sort自己测试。 ### 步长序列 步长的选择是希尔排序的重要部分。不同的步长时间会有所不同。 我们一般会选择每次步长除以$2$或$3$。 ### 性质 希尔排序是一种不稳定的排序，希尔排序的最优时间复杂度为 $O(n\log n)$，当 步长每次除以 $3$ 时，时间复杂度为 $O(n^{\frac{3}{2}})$。当前最好的步长选择的最坏时间复杂度为 $O(n\log^2 n)$，空间复杂度为 $O(n)$。 ### 实现 代码可以在这里测试：[Luogu P1177 【模板】快速排序](https://www.luogu.com.cn/problem/P1177) 步长每次除以 $3$，数组下标从 $1$ 开始代码： ```c++ int h=1; while (h<n/3) h=h*3+1; while (h) { for (int i=h+1; i<=n; i++) for (int j=i; j>h && a[j]<a[j-h]; j-=h) swap(a[j], a[j-h]); h/=3; } ``` ## 参考 1. [维基百科](https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F) 2. [OI-Wiki](https://oi-wiki.org/basic/shell-sort/) 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏