P1177 【模板】排序 题解
Crab_Tang
·
·
题解
这里介绍希尔排序
前置芝士：插入排序没看见别怪我
希尔排序是插入排序的一种优化算法。以他的发明者贝壳希尔（Shell）命名。
希尔排序的过程：
- 把原序列划分为几个每个元素间距相等的子序列。（每组元素间的距离称作梯度）
- 对每个子序列进行插入排序（梯度为原序列长度时不做，因为每组只有一个元素，做了也没有意义）
- 缩小梯度，重复上述步骤直到梯度为1
希尔排序的思想：
插入排序在有序时最快。通过前面间距较小的插入排序，序列一步步变得有序。
经典选取梯度方式及其时间复杂度
梯度 T=\{2^k-1|k=1,2,...,{\left \lfloor{ \log_2 n}\right \rfloor}\}。在程序实现时一般先设最大值，再逐渐缩小。这种选取梯度的方法时间复杂度为 O(n^{3/2})。
具体证明请看OI-WIKI。
例：
- 序列：7,6,5,4,3,2,1,0。
- 序列长度：8。
- 最初梯度：8。
- 梯度每次缩小方式：tidu\gets \left \lfloor \frac{tidu}{2}\right \rfloor 。
- 排序方式：升序
第一轮取梯度为 8，不做。
第二轮取梯度为 4(\left \lfloor \frac{8}{2}\right \rfloor)，进行插入排序：
插入排序后序列：$3,2,1,0,7,6,5,4$。
第三轮取梯度为 $2(\left \lfloor \frac{4}{2}\right \rfloor)$，进行插入排序：
$3,1,7,5$ 为一组，$2,0,6,4$ 为一组。
插入排序后序列：$1,0,3,2,5,4,7,6$。
第三轮取梯度为 $1(\left \lfloor \frac{2}{2}\right \rfloor)$，进行插入排序：
$1,0,3,2,5,4,7,6$ 为一组。
插入后序列：$0,1,2,3,4,5,6,7$。
排序完毕。
## 空间复杂度：
空间复杂度为 $O(1)$。
## 代码
### 主函数部分
~~太简单了不给了。~~
### 子排序部分
这部分的代码其实跟插入排序差不多。
只不过下标为 $i$ 的下一个元素是 $i+梯度$ 罢了。
~~自己改改插入排序就好了不给了代码~~
### 缩小梯度部分
```cpp
void shellsort(){//左闭右开
int _tidu=(1<<int(log2(n)));//最开始的梯度是比n小最大的2的k次方
while(_tidu>=1){//此处注意，梯度为1时也要做一遍子排序
sub_shellsort(_tidu);//执行子插入排序
_tidu=_tidu/2;//梯度每次缩小为二分之一是一种比较经典的选梯度方式
}
return ;
}
```
[参考代码](https://www.luogu.com.cn/paste/xuele4tr)