对Shell排序算法的理解

Shell排序算法的基础是插入排序算法，所以在开始讲Shell排序算法之前，先讲讲插入排序算法。

我们先来看一个简单的小问题，给出一个已经排序好的数组arr以及另外一个数字n，如何将n放入到数组arr中，使得放入n后arr内的所有数字依然是有序的？

int arr[10] = {3,4,7,8,10,33,56,66,100};
int n = 47;

显然我们想要的结果是{3,4,7,8,10,33,47,56,66,100}，那么具体该怎么做呢？很容易就可以想到，最简单的做法就是从数组中最大的数字开始往前，让n依次和数组中的数字做比较，每次遇到比n大的数字，就让n在数组中的位置前移，直到遇到不大于n的数字为止。也就是下面写的那样。

arr[9] = n;
for(int i = 9;i >= 1;--i)
{
    if(arr[i - 1] > arr[i])
    {
        int t = arr[i];arr[i] = arr[i - 1];arr[i - 1] = t;
    }
}

然后想想:如果一个数组只有一个元素的话，那这个数组是不是可以直接被认为是有序的呢？然后我们把另外一个数字通过以上方式插入到这个只有一个元素的数组，那么我们就得到了有两个元素的有序数组。再以相同的方式插入第3个数字，就得到了有3个元素的有序数字。然后继续以相同的方式插入第4个、第5个......直到第n个，我们就得到了含有n个元素的有序数组。于是，给我们任意一组数字，我们都可以按照这样的思路把这些数字依次插入到一个数组中去，这样我们就完成了对这些数字的排序。这就是插入排序算法的原理。

以下就是插入排序算法的一种常见的实现方法。

void insertSort(int* arr,int nItem)  //nItem:数组内元素的个数
{
    for(int i = 1;i < nItem;++i)
    {
        for(int j = i;j >= 1 && arr[j - 1] > arr[j];--j)
        {
            int t = arr[j];arr[j] = arr[j - 1];arr[j - 1] = t;
        }
    }
}

如果一个数组中的元素比较接近有序的话，使用插入排序算法会很快。但是如果数组中某个元素离它应该被插入的位置很远的话，显然插入排序算法就会比较慢了，因为插入排序算法只能让一个元素每次只移动1个步长。如果说能够增加元素移动的步长的话，那么排序的速度应该就能变快。Shell排序算法就是这么做的。

这里就先直接上Shell排序算法的代码。这里给出的实现方式并非最好的实现方式，但是这个实现方式看起来比较简单，易于理解，所以这里以这种实现方式为基础进行讲解。

void shellSort(int* arr,int nItem)
{
    for(int gap = nItem / 2;gap > 0;gap /= 2)
    {
        for(int i = gap;i < nItem;++i)
        {
            for(int j = i;j >= gap && arr[j - gap] > arr[j];j -= gap)
            {
                int t = arr[j];arr[j] = arr[j - gap];arr[j - gap] = t;
            }
        }
    }
}

这段代码第一眼看上去感觉不好理解。但是我们知道，Shell排序算法的基础是插入排序算法，所以Shell排序算法的代码有一部分其实跟插入排序算法的代码是很像的。如果我们把Shell排序算法最外层的循环去掉，只剩下里面的两层循环的话，我们就会发现Shell排序算法和插入排序算法之间相似的地方。

下面是Shell排序算法内部的两层循环，以及插入排序算法的代码。请对比一下两者之间的异同。

/*Shell排序算法内部的两层循环*/
for(int i = gap;i < nItem;++i)
{
    for(int j = i;j >= gap && arr[j - gap] > arr[j];j -= gap)
    {
        int t = arr[j];arr[j] = arr[j - gap];arr[j - gap] = t;
    }
}

/*插入排序算法的代码*/
for(int i = 1;i < nItem;++i)
{
    for(int j = i;j >= 1 && arr[j - 1] > arr[j];--j)
    {
        int t = arr[j];arr[j] = arr[j - 1];arr[j - 1] = t;
    }
}

容易发现，只要把Shell排序算法内部的两层循环中的"gap"替换成"1"就可以得到插入排序算法的代码了。所以，把"1"替换成"gap"会让代码的功能产生什么变化呢？

其实Shell排序算法内部的两层循环做的事情是对数组的子数组进行排序，那么它是对什么样的子数组进行排序呢？下面我们把被Shell排序内部两层循环排序的子数组全部列出来。

//被排序的子数组1
arr[0],arr[gap],arr[2 * gap],arr[3 * gap],......

//被排序的子数组2
arr[1],arr[1 + gap],arr[1 + 2 * gap],arr[1 + 3 * gap],......

//被排序的子数组3
arr[2],arr[2 + gap],arr[2 + 2 * gap],arr[2 + 3 * gap],......

//......

//被排序的子数组gap
arr[gap - 1],arr[gap - 1 + gap],arr[gap - 1 + 2 * gap],arr[gap - 1 + 3 * gap]......

对照Shell排序算法内部两层循环的代码，看一看上面列出来的子数组，思考一下，看看自己能不能理解。如果不能理解的话，下面就举一个具体的例子。

例如，有一个数组arr，其中的元素为{4,2,3,8,4,6,8,3,2,6,3,2,3,5,7,6,4}。如果对该数组执行Shell排序算法内部两层循环的操作(假设gap == 3)，那么接下来用红色标记出被排序的子数组。

被排序的子数组1: {4,2,3,8,4,6,8,3,2,6,3,2,3,5,7,6,4}

被排序的子数组2: {4,2,3,8,4,6,8,3,2,6,3,2,3,5,7,6,4}

被排序的子数组3: {4,2,3,8,4,6,8,3,2,6,3,2,3,5,7,6,4}

将这些子数组排序后，得到的结果就是{3,2,2,4,3,2,6,3,3,6,4,6,8,4,7,8,5}。对照着内部两层循环的代码，手写一下代码执行的过程，看看是不是跟上面所说的一致。明白了内部两层循环代码的执行过程后，我们容易发现，子数组中相邻的元素在原来的数组中的位置的间隔其实就是gap - 1，而且内部两层循环就是使用插入排序算法对子数组进行排序的。

现在我们就可以结合最外层的循环来看整个Shell排序算法了。我们发现，最外层循环其实就是在给变量gap依次取不同的值，gap一开始的取值为整个数组长度的一半，然后每次的取值都为上一次取值的一半。每次gap的值改变后，内部两层循环就以新的gap的值作为间隔来寻找子数组，并对这些子数组进行排序。gap的最终取值总是1，所以整个Shell排序算法在最后总会对整个数组进行一次插入排序算法。这就是Shell排序算法的流程。

Shell排序算法相比插入排序算法有什么优越性呢？第一，Shell排序算法通过gap这一变量增加了插入排序算法中元素每次移动的步长，这样就加快了速度。第二，之前说过，插入排序算法对一个接近有序的数组的排序速度是比较快的。内部两层循环每次对子数组排序后，整个数组相比原来就变得更加有序，在这种情况下再使用插入排序算法对数组进行排序，速度会更快。以上两点就是Shell排序算法比插入排序算法更加优越的原因。