希尔排序（Shell sort），也称为缩小增量排序法，是插入排序的一种改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
排序对不相邻的记录进行比较和移动：
- 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）
- 对这些子序列进行插入排序
- 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1
最开始时，按照间隔为
size()的一半来选取元素进行分组，每一组采用快速排序，完成后，将间隔更改为上次间隔的一半，继续进行分组快速排序，直到间隔为 1，对整个数组进行一次快速排序，即可完成排序：
希尔排序是一种不稳定的排序算法。
时间复杂度：希尔排序的最优时间复杂度为。希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取（就是间距如何减小到 1）有关，比如「间距每次除以 3」的希尔排序的时间复杂度是 。已知最好的最坏时间复杂度为。
空间复杂度：希尔排序的空间复杂度为。
代码实现