好了，为了能够真正弄明白希尔排序的算法，我们还是老办法——模拟计算机在执行算法时的步骤，还研究算法到底是如何进行排序的。

    希尔排序算法代码如下。

    1. /* 对顺序表L作希尔排序 */
    2. void ShellSort(SqList *L){
    4.     int i, j;
    5.     int increment = L->length;
    7.     do{
    9.         /* 增量序列 */
    10.         increment = increment / 3 + 1;
    12.         for (i = increment + 1; i <= L->length; i++){
    14.             if (L->r[i] < L->r[i - increment]){
    16.                 /* 需将L->r[i]插入有序增量子表 */
    17.                 /* 暂存在L->r[0] */
    18.                 L->r[0] = L->r[i];
    20.                 for (j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment)
    21.                     /* 记录后移，查找插入位置 */
    22.                     L->r[j + increment] = L->r[j];
    24.                 /* 插入 */
    25.                 L->r[j + increment] = L->r[0];
    26.             } 
    27.         } 
    28.     }
    29.     while (increment > 1);
    30. }
    1. 程序开始运行，此时我们传入的SqList参数的值为length=9,r[10]={0,9,1,5,8,3,7,4,6,2}。这就是我们需要等待排序的序列，如图9-6-4所示。

    image.png

    1. 第4行，变量increment就是那个“增量”，我们初始值让它等于待排序的记录数。
    2. 第5～19行是一个do循环，它提终止条件是increment不大于1时，其实也就是增量为1时就停止循环了。
    3. 第7行，这一句很关键，但也是难以理解的地方，我们后面还要谈到它，先放一放。这里执行完成后，increment=9/3+1=4。
    4. 第8～17行是一个for循环，i从4+1=5开始到9结束。
    5. 第10行，判断L.r[i]与L.r[i-incre-ment]大小，L.r[5]=3小于L.r[i-increment]=L.r[1]=9，满足条件，第12行，将L.r[5]=3暂存入L.r[0]。第13～14行的循环只是为了将L.r[1]=9的值赋给L.r[5]，由于循环的增量是j=increment，其实它就循环了一次，此时j=-3。第15行，再将L.r[0]=3赋值给L.r[j+increment]=L.r[-3+4]=L.r[1]=3。如图9-6-5所示，事实上，这一段代码就干了一件事，就是将第5位的3和第1位的9交换了位置。

    image.png

    1. 循环继续，i=6，L.r[6]=7>L.r[i-increment]=L.r[2]=1，因此不交换两者数据。如图9-6-6所示。

    image.png

    1. 循环继续，i=7，L.r[7]=4<L.r[i-incre-ment]=L.r[3]=5，交换两者数据。如图9-6-7所示。

    image.png

    1. 循环继续，i=8，L.r[8]=6<L.r[i-incre-ment]=L.r[4]=8，交换两者数据。如图9-6-8所示。

    image.png

    1. 循环继续，i=9，L.r[9]=2<L.r[i-incre-ment]=L.r[5]=9，交换两者数据。注意，第13～14行是循环，此时还要继续比较L.r[5]与L.r[1]的大小，因为2<3，所以还要交换L.r[5]与L.r[1]的数据，如图9-6-9所示。

    image.png
    最终第一轮循环后，数组的排序结果为图9-6-10所示。细心的同学会发现，我们的数字1、2等小数字已经在前两位，而8、9等大数字已经在后两位，也就是说，通过这样的排序，我们已经让整个序列基本有序了。

    这其实就是希尔排序的精华所在，它将关键字较小的记录，不是一步一步地往前挪动，而是跳跃式地往前移，从而使得每次完成一轮循环后，整个序列就朝着有序坚实地迈进一步。
    image.png

    1. 我们继续，在完成一轮do循环后，此时由于increment=4>1因此我们需要继续do循环。第7行得到increment=4/3+1=2。第8～17行for循环，i从2+1=3开始到9结束。当i=3、4时，不用交换，当i=5时，需要交换数据，如图9-6-11所示。

    image.png

    1. 此后，i=6、7、8、9均不用交换，如图9-6-12所示。

    image.png

    1. 再次完成一轮do循环，increment=2>1，再次do循环，第7行得到increment=2/3+1=1，此时这就是最后一轮do循环了。尽管第8～17行for循环，i从 1+1=2开始到9结束，但由于当前序列已经基本有序，可交换数据的情况大为减少，效率其实很高。如图9-6-13所示，图中箭头连线为需要交换的关键字。

    image.png
    最终完成排序过程，如图9-6-14所示。
    image.png