首先我们看一段希尔排序的C实现代码：
图1 希尔排序C实现（选自 W. Rich的《C语言编程》）
从这段代码的逻辑来看，只能使用三种嵌套循环结构（我们分别称之为外循环、中循环、内循环）来实现希尔排序，但我们不能简单地阅读代码。 了解排序过程中每个位置的元素所发生的变化，这样我们就无法很好地理解希尔排序的整个过程，这可能会导致我们理解的希尔排序与实际的希尔排序存在差异。 它们之间存在偏差（掌握了错误的排序方法）。
为了准确理解希尔排序，我们需要用事实说话。 最直接的方式就是在上面的代码中添加一条打印语句，这样我们就可以立即知道程序在这一步做了什么，以及每次排序行为发生后交换了哪些元素。
这里我们选择对数组{9,8,7,6,5,4,3,2,1,0}进行升序排序。 排序结果应为{0,1,2,3,4,5,6,7,8,9}。
首先，打印这些元素的排序顺序：
图2 排序前打印结果
第一次进入外循环时，gap=5，进入内循环后，第一次交换下标0和下标5位置的元素（因为gap为5，满足内循环判断条件是位置0的元素的值大于位置5）的元素的值。 第二次交换了位置 1 和 6 的元素。 第三次交换了位置 2 和位置 7 的元素。 的元素，同理，第四次交换3和8，第五次交换4和9。 此时再次进入内循环时，不满足条件j>=0，第一轮内循环结束。 如下图3所示：
图3gap=5时的排序过程
这时候你可能要问，如果不满足内循环中的条件v[j]>v[j+gap]怎么办？ 好像中间循环还没用过？ 如果每组等距位置的元素顺序是正确的，如何保证与其他组的顺序也是正确的？ 别担心，我们把gap缩小一半，当gap=2的时候我们就会遇到使用中间循环的情况。 了解这个过程就能很好地解决上述问题，并准确理解希尔排序。 开始吧。
当gap=2时，根据上一步的排序结果，进入内循环，第一次交换位置0和2的元素，第二次交换位置1和3的元素，第三次交换2。 对于位置4的元素，当前位置原则与上一步相同。 但第四次我们发现位置3和位置5的元素不满足条件v[j]>v[j+gap]，所以内循环退出。 进入中循环后，进入内循环（相当于开始比较位置0和2、1和3、2和4处的元素的过程。这样会检查之前组之间的错误顺序关系。在 In在本例中，前一个结果的位置 0 和 2 处的元素被交换）。 交换位置0和位置2的元素后，内循环交换位置1和位置3的元素时不满足v[，满足条件j]>v[j+gap]，所以再次进入中间循环，并且然后进入内循环。 每次调用内循环时，内循环中间循环中i的值就加1，直到满足内循环中的条件v[j]>v[j+gap]（本例中为内循环1位置开始变化）从位置5）开始比较，所以第五次开始比较位置5和7的元素顺序是否正确，那么第六次是6和8，第七次是7、9，第八次又出现了第四次出现的情况。 此时由于中间循环中i值的变化，不再需要检查第5个元素之前的组间元素是否正确，所以第八次从第5个位置的元素开始，到检查和交换。 位置5和位置7的元素进入内循环时将不再满足条件v[j]>v[j+gap]。 该流程如下图4所示：
图4 当gap=2时的排序过程
用文字来描述图4的流程真是一大段，看起来相当头疼。 其实没必要从字面上理解。 如果您根据图1中的程序和图4中的运行结果来思考，您将很快理解排序过程。 简单来说，就是满足内循环条件时进行排序操作。 当不满足内循环条件时，使用中间循环检查之前未检查的排序结果是否正确，并依靠内循环调整不正确的顺序（当然是指除了间隙之外的两个元素）直到进入下一个满足条件的内循环继续排序操作（此时之前的元素都已检查完毕）。
最后，我们将间隙值减小为 1 以进行最后一次排序。 这时我们发现每次进入内循环时都不满足条件v[j]>v[j+gap]，所以没有进行元素交换。 如下图5所示：
图5gap=1时的排序过程
最后打印出最终的排序结果如下图6所示：
图6 最终排序结果
好了，整个希尔排序的流程就介绍完了。 最后我们来介绍一下什么是希尔排序。 希尔排序是插入排序的一种，但是当前一个缩减量取较大值时，需要使用一个缩减量来不断约束排序结果的粗糙度（一般看起来是有顺序的，但有些排序错误的是穿插）。
代码：
