希尔排序
✍基本思想|演示|算法代码|性能
基本思想
希尔排序(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)
领取专属 10元无门槛券
私享最新 技术干货