POJ1017希尔排序

POJ1017是一个关于希尔排序的问题。希尔排序是一种插入排序的变种，也称为缩小增量排序。其基本思想是将待排序的数组按照一定的增量分成若干子序列，分别对这些子序列进行插入排序。随后，逐渐减小增量，继续按照此方法排序，直至增量为1，即对整个数组进行插入排序。

具体来说，希尔排序可以通过以下步骤实现：
1. 选择一个增量序列t1, t2, …, tk, 其中ti>tj, tk=1；
2. 按增量序列个数k，对序列进行k趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列；
4. 分别对各子表进行插入排序；
5. 合并各子序列，得到完整的有序序列。

希尔排序是一种高效的排序算法，其时间复杂度取决于所选取的增量序列。通常来说，增量序列可以选择使用Knuth提出的增量序列：1, 4, 13, 40, …，时间复杂度为O(N^(3/2))。