经典排序算法——希尔排序

希尔排序

✍基本思想|演示|算法代码|性能

基本思想

希尔排序（Shell Sort）是插入排序算法的一种改进版本，又称为缩小增量排序。

希尔排序把下标按照一定的增量（gap=n/2）进行分组，然后分别对每个组内的数据进行直接插入排序，不断缩小增量进行排序，直至gap=1时，对整组数据进行直接插入排序。

以数据8、5、2、4、1、7、6、3为例

首先对数据进行分组，间隔gap=n/2=4，同色的为同一组，如上图所示，对组内数据进行直接插入排序，如下图

以间隔gap=2进行分组，如上图所示，对组内数据进行直接插入排序，如下图

以间隔gap=1进行分组，如上图所示，其实就是对整组数据进行直接插入排序，排序完后的数据如下图

C++代码

Python代码

Java代码

希尔排序是一种不稳定的排序算法，其时间复杂度与增量的选取有关，平均时间复杂度为O(N1.3)，空间复杂度为O(1)