希尔排序

定义

希尔排序(Shell Sort)由 Donald Shell 于 1959 年提出,是最早突破 O(n²) 的排序算法之一。它按一系列递减的增量(gap)对数组分组做插入排序,最后以增量 1 收尾。

原理

增量为 h 时,把数组视作 h 个交错的子序列分别插入排序,使元素能一步移动 h 个位置,快速接近最终位置;随着增量缩小,数组越来越接近有序,而插入排序对近有序数据非常快。性能高度依赖增量序列:Shell 原始的 n/2 序列最坏 O(n²),Hibbard、Sedgewick 等序列可达 O(n^1.5) 甚至更好,精确平均复杂度至今没有完整理论刻画。

应用

嵌入式与内存受限环境常用(如 uClibc 的 qsort 实现),因其无需递归与额外空间、代码短小。

优缺点

原地排序、实现简单、对中小规模数据表现好;缺点是不稳定,且大规模数据下不敌快速排序与归并排序。