c语言数据结构_排序_希尔排序

    首先我们先来看一段希尔排序的c实现代码：

    从这段代码的逻辑来看仅仅需要三次相互嵌套的循环结构（我们分别称为外层循环，中间循环，内层循环）就可以实现希尔排序了，但只是简单的阅读代码我们并不能体会到各个位置上的元素在排序过程中都发生了哪些变化，从而我们无法很好的理解整个希尔排序进行的过程，很可能导致我们理解的希尔排序与实际上真正的希尔排序之间出现偏差（掌握了错误的排序方法）。

    为了能准确理解希尔排序，我们需要用事实说话。最直接的方法就是在上面的代码中加入打印语句，这样我们就可以在每次的排序行为发生之后马上知道程序在这一步做了什么，交换了哪些元素。

    这里我们选择对{9,8,7,6,5,4,3,2,1,0}这个数组进行升序排序，排序结果应该是{0,1,2,3,4,5,6,7,8,9}。

    首先打印了这些元素排序之前的顺序：

    在第一次进入外层循环时gap=5，进入内层循环后第一次交换了下标为0与下标为5两个位置上的元素（因为间隔gap是5，而且满足内层循环的判断条件，0号位置上元素的值大于5号位置上元素的值），第二次交换了下标为1与下标为6位置上的元素，第三次交换了2与7位置上的元素，同理，第四交换了3与8，第五次交换了4与9。这时再进入内层循环时j>=0这个条件不满足了，第一轮的内层循环结束了。如下图3所示：

    这时你可能要问了，如果内层循环中v[j]>v[j+gap]这个条件不满足了增么办呢？中间循环好像还没有用到呀？每组相等间距的位置上的元素的顺序排对了，可和其它组之间顺序也是对的应当如何确保呢？不要着急，让我们把间距再缩小一半，及当gap=2时我们就会遇到使用中间循环的情况，体会这个过程将很好的解决上面的疑问，并且能准确理解希尔排序。让我们开始吧。

    当gap=2时，基于上一步的排序结果，进入内层循环第一次交换了0位置与2位置上的元素，第二次交换了1与3位置上的元素，第三次交换了2与4位置上的元素，到目前位置原理都与上一步是相同的。但是第四次我们发现3与5位置上的元素不满足v[j]>v[j+gap]这个条件了，于是内层循环退出了。进入中间循环之后又进入了内层循环（相当于又开始了去比较0与2,1与3,2与4位置上的元素这个过程了，这就检查了之前错误的组间顺序关系，在这个例子中交换了上个结果第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过程洋洋洒洒一大段，看起来也挺头疼的。其实没有必要咬文嚼字的理解，结合着图1的程序和图4的运行结果稍微思考一下也是会很快理解这个排序过程的。简单来说就是内层循环条件满足就进行排序操作，内层循环条件不满足时就用中间循环检查之前没检查过的排序结果是否正确，依靠内层循环把顺序不对的调整过来（当然是指相距gap的两个元素），直到进入下一个满足条件的内层循环继续进行排序操作（这时之前的元素都是被检查过的）。

    最后我们把gap的值减小为1进行最后一次排序，这时我们发现进入内层循环时v[j]>v[j+gap]这个条件每次都不满足，因此没有元素被交换。如下图5所示：

    最后打印出最终的排序结果如下图6所示：

    好了，整个希尔排序的过程已经全部介绍完了。最后介绍一下希尔排序是什么，希尔排序是插入排序的一种，但其中需要用到一个缩小量来不断约束之前这个缩小量取较大值时排序结果的毛糙感（大体上看着有个顺序，但又有些错误的排序穿插其中）。

程序代码：