Data structures and sorting: Hilbert sort. Hilbert sort is a comparison-based sorting algorithm that sorts data by comparing individual elements.

该算法在实现上较为简便，在数据规模较小时展现出较高的效率水平；然而当数据规模较大时若待排序序列已按关键字值基本有序，则其效率仍保持较高的水平可达到O(n)水平。希尔排序正是基于这两个方面展开研究和改进的方法。

希尔排序（Shell Sort）又称为“缩小增量排序”，有D. L. Shell在1959年首先提出来。

基本思想

选取一个小于n的第一个整数d₁作为初始增量，并将文件中的所有记录按一定规则分成若干小组。随后将相距d₁倍数的所有记录归入同一小组内执行直接插入排序操作；接着依次选取一系列递减至1的增量序列d₂, d₁（其中满足条件dt-1<…<d₂<d₁），并重复上述步骤直至最后一个增量dt=1时，在整个数据集中完成最后一次直接插入排序处理工作为止。这种方法实质上属于逐步细化排序的方法。

主要步骤

1. 确定一个增量序列{d₀, d₁, … ,d_{k−₁}}
2. 基于当前增量di将n条记录划分成di个子表，并使各子表中数据项的下标间隔为di
3. 对各子表内的数据执行直接插入排序
4. 依次取i=0, 1,…, k−1并反复执行