首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

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

希尔排序

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

基本思想

希尔排序(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 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券