本文共 463 字，大约阅读时间需要 1 分钟。

目录

一、概述

希尔排序是在插入排序基础上，优化而来，时间复杂度为O(n **3/2),空间复杂度O(1), 稳定排序

二、重点

实际的时间复杂度，与对应的序列算法有很大的关系，常见的序列有：

1.简单序列

使用step=size/2， 每次再step = step/2，直到为0截止

2.hibbard序列，最坏O(n **3/2), 平均O(n **5/4)

先求step：

step=1;

while(step < size/2) step = step*2+1;

3.sedgewick序列：

一种算法是

9*(4**i) - 9*(2**i) +1 or (4**i) - 3* (2**i) + 1

在网上（见参考【2】有看到直接使用以下用法，测试效果也还可以：

step=1; while(step < size/3) step = step*3+1;

三、场景：

数据量不是很大，又没有外部依赖，不想写复杂的代码，可使用较好序列的希尔排序。

四、参考文档：

【1】希尔排序增量序列简介 

【2】算法-7-希尔排序

转载地址：http://vopbi.baihongyu.com/