| 算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 希尔排序 | O(n^1.3) | O(n) | O(n^2) | O(1) | In-place | 不稳定 |
稳定：如果A原本在B前面，而A=B，排序之后A仍然在B的前面；
不稳定：如果A原本在B的前面，而A=B，排序之后A可能会出现在B的后面；
时间复杂度： 描述一个算法执行所耗费的时间；
空间复杂度：描述一个算法执行所需内存的大小；
n：数据规模；
k：“桶”的个数；
In-place：占用常数内存，不占用额外内存；
Out-place：占用额外内存。
希尔排序是将数据分组，将每一组进行插入排序。每一组排成有序后，最后整体就变有序了。希尔排序也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
详细过程查看如下博客链接：
排序算法 —— 希尔排序（图文超详细）
算法步驟：
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。