Question

shell排序法是怎么实现？有关键码（16，9，4，25，15，2，13，18，17，5，8，24）递增次序，接下..

用初始增量为4的shell排序法，一趟扫描后的结果为？请给出详细步骤。谢谢

Answer 1

一趟扫描后结果为 15 2 4 18 16 5 8 24 17 9 13
分析过程如下：
因为增量gap = 4，所以把位置相差为4的取出分成组如下
16 15 5
9 2 5
4 13 8
25 18 24
对这三组数分别进行插入排序，得到第一次扫描后的结果。
后面要做的就是减小增量，重新分组，对每组数在进行插入排序，直到增量为1，进行最后
一次插入排序后完成整个排序过程。
希尔排序的思想是通过前面的处理，使数据的无序性降低，从而使后面在进行插入排序时需要进行的比较和插入次数减小。时间复杂度大约n ^ 1.2
网上有很多这方面的文章（我文章里就有个简单的示例程序^_^)，楼主可以多搜些资料看看。