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

希尔排序

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

基本思想

希尔排序(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)

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180821G0APDP00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券