【排序算法】一文教你从零学会希尔排序

一、插入排序的基本思想

希尔排序是插入排序的一种，在介绍希尔排序之前，先介绍一下插入排序的思想。插入排序就是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。与扑克牌的插入的类似。

二、直接插入排序

直接插入排序是实现希尔排序的基础，本人的理解其实希尔排序就是直接插入排序的升级版本，我们先介绍和实现以下直接插入排序，为实现希尔排序打下基础。

2.1思想

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

2.2代码实现与解释

void InsertSort(int* a, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int endi = i;
        int tmp = a[endi + 1];
        while (endi >= 0)
        {
            if (a[endi] > tmp)
            {
                a[endi + 1] = a[endi];
            }
            else
                break;
            endi--;
        }
        a[endi + 1] = tmp;
    }
}

代码中的a是传进来的整形数组，n是数组元素的个数。我以下面这个例子来更加形象地解释一下上面的代码。假设要将5,4,3,2,1这个数组调整为升序，n为5，数组的下标分别为0,1,2,3,4。

for循环的第一趟循环，为的就是让数组的前两个数有序。第一趟i=0，endi=i=0,tmp=a[1]=4（tmp的作用就是保存要插入前面序列的那个数的值）,a[endi]（第一个数）比tmp（第二个数的值）大，将 a[endi]的值赋给a[endi + 1]（相当于往后挪了，空出位置可以让tmp的值插入）。如果a[endi] > tmp这个条件不成立，就证明tmp（要插入数字的值）大于等于前面序列的值，也就不用往前插入了，直接break。endi不断减减，比tmp大的数就不断往后挪一格，最后endi+1这个位置就是tmp这个值应该去的位置。（就第一趟排序而言，endi本身为0，减减后变为-1，endi+1==0正好是tmp要在的位置）。之后endi不断往后挪，endi后面的一个数不断往前插入。n个数要走n-1趟，所以for循环中的条件是i<n-1。

三、希尔排序

3.1思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有数分成各组，所有距离相同的数分在同一组内，并对每一组内的记录进行排序。然后再取距离，重复上述分组和排序的工作。当距离到达=1****时，所有数在统一组内就排好序了。

有人可能就会问了，为什么要取一定距离来分组呢？原因是因为插入排序在序列越有序的情况下效率越高，从上面直接插入排序我们就可以看出了，当要插入的序列已经有序而且要插入的数比要插入的序列的最后一个数大时，只需要比较一下就可以从循环中break，大大提高了算法效率。分组就是为了让小的数尽快到前面，大的数尽快到后面（针对要将序列排成升序序列来说），尽快让数组接近有序，从而提高算法效率。过程如下图所示：

3.2代码实现与解释

void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++)
        {
            int endi = i;
            int tmp = a[endi + gap];
            while (endi >= 0)
            {
                if (tmp < a[endi])
                a[endi + gap] = a[endi];
                else
                    break;
                endi -= gap;
            }
            a[endi + gap] = tmp;
        }
    }
}

希尔排序实现的本质思路其实与直接插入排序相同，只是希尔排序当中加入了分组的思想。最后当gap == 1时，就是直接插入排序。在这里要说明一下，为什么for循环中的限定语句要写成i < n - gap？原因是为了让tmp = a[endi + gap]中endi+gap的数组访问不越界。

看上图，数组是10个元素，n==10，gap==4，i<6，最后一组的tmp = a[endi + gap]中endi+gap==9刚好不越界。

3.3希尔排序的特性总结

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。

但有一点可以肯定的是，希尔排序在处理接近有序的数列的时候效率很高！