插入排序与希尔排序优化思路

本篇针对插入排序和希尔排序来讲优化思路，有部分内容因为前一篇文章已经有交代，这里不重复，如果你还没有看，请先看前一篇。我们来看插入排序的动图演示

插入排序保证前面一块是有序的情况下，新增的一个元素通过向前交换到合适的位置，所以叫做插入排序。

插入排序基本实现

我们先来看插入排序的基本实现

void insert_sort(sort_element_t * beg, sort_element_t * end)
{
    for (sort_element_t* i = beg + 1; i < end; ++i)
    {
        sort_element_t val = *i;
        sort_element_t* j = i;
        for (; j > beg && val < j[-1]; --j)
        {
            *j = j[-1];
        }
        *j = val;
    }
}

插入排序即使不做任何优化，效率也明显高于上篇所说的冒泡排序和选择排序。那么按照惯例，先上双向看看效果

插入排序优化，双向插入

不过双向版本的插入排序可能并不是你想象中那么好写，甚至于有点不太好懂

void double_insert_sort(sort_element_t * beg, sort_element_t * end)
{
    if (end - beg > 1)
    {
        for (sort_element_t* i = beg + 1, *j = end - 1; ; )
        {
            sort_element_t val = *i;
            sort_element_t* t = i;
            for (; t > beg && val < t[-1]; --t)
            {
                *t = t[-1];
            }
            *t = val;

            if (++i > j)
            {
                if (*i < *j)
                    ++j;
                else
                    break;
            }

            val = j[-1];
            t = j;
            for (; t < end && *t < val; ++t)
            {
                t[-1] = *t;
            }
            t[-1] = val;

            if (i > --j)
            {
                if (*j < j[-1])
                    --i;
                else
                    break;
            }
        }
    }
}

我们来看看测试结果，在 VS2015 下对 45000 个int排序

这个优化效果非常不明显，有种吃力不讨好的感觉。那么，我们换个方法，来试试加大步长吧，这个变动让算法有了另一个名字

希尔排序

希尔排序的坑特别深，你需要有心理准备。希尔排序和梳排序类似，都是通过使用较大的步长让元素更快速地到达正确位置附近

不过在步长的选择上，希尔排序与梳排序差别巨大。首先梳排序的步长选择较为简单，每次乘以0.8即可，这个数字就不要管怎么来的了，我也不知道。梳排序的研究资料较少，但希尔排序则不一样，步长选择的研究非常多，也就是说光是步长的选择就是一门学问，这就是一个大坑，而且这个步长选择对性能的影响十分明显。我们先来看最早的希尔排序版本，最早的版本使用步长每次乘以0.5。

void shell_sort_0_5(sort_element_t * beg, sort_element_t * end)
{
    if (end - beg > 1)
    {
        size_t incre = (size_t)(end - beg) / 2;
        for (; incre >= 1; incre /= 2)
        {
            sort_element_t * bound = beg + incre;
            for (sort_element_t * i = bound; i < end; ++i)
            {
                sort_element_t * p = i;
                sort_element_t val = *i;
                for (; p >= bound && val < *(p - incre); p -= incre)
                    *p = *(p - incre);
                *p = val;
            }
        }
    }
}

后来，Pratt 与 Knuth 改进了新的步长序列
1, 4, 13, 40, 121, ...
得到以下代码

void shell_sort(sort_element_t * beg, sort_element_t * end)
{
    if (end - beg > 1)
    {
        size_t incre = 1;
        while (incre < (size_t)(end - beg - 1) / 3)
            incre = incre * 3 + 1; // A003462, Pratt, 1971, Knuth, 1973
        for (; incre >= 1; incre /= 3)
        {
            sort_element_t * bound = beg + incre;
            for (sort_element_t * i = bound; i < end; ++i)
            {
                sort_element_t * p = i;
                sort_element_t val = *i;
                for (; p >= bound && val < *(p - incre); p -= incre)
                    *p = *(p - incre);
                *p = val;
            }
        }
    }
}

更多关于步长的研究可以参考维基百科，本篇不对步长做讲解。后文的优化将使用这个版本的代码

希尔排序优化，运用带哨兵的插入排序

带哨兵的插入排序是什么东西？其实就是指以下这样的插入排序

void unguarded_insert_sort(sort_element_t * beg, sort_element_t * end)
{
    for (sort_element_t* i = beg + 1; i < end; ++i)
    {
        sort_element_t val = *i;
        sort_element_t* j = i;
        for (; val < j[-1]; --j)
        {
            *j = j[-1];
        }
        *j = val;
    }
}

和前面的插入排序的区别在哪？就是少了j > beg &&，不做边界判断。不做边界判断确实能运行得更快，但不会越界吗？我们来考虑以下这种情况
int arr[8] = {-1, 8, 9, 4, 5, 6, 1, 6};
然后我们排序的时候写unguarded_insert_sort(arr + 1, arr + 8);它就能正确排序而且不会发生越界，因为最前面存在比需要排序的元素都要小的数，而那个数就是哨兵，它充当着让内循环退出的作用，也就是说，在调用这个函数的时候，只要保证beg的左边存在比右边都要小的元素就行了。

有了这个能怎么优化呢？我们把步长1的部分单独拆出来，写成下面这样

void shell_sort_o1(sort_element_t * beg, sort_element_t * end)
{
    if (end - beg > 1)
    {
        size_t incre = 1;
        while (incre < (size_t)(end - beg - 1) / 3)
            incre = incre * 3 + 1; // A003462, Pratt, 1971, Knuth, 1973
        for (; incre > 1; incre /= 3)
        {
            sort_element_t * bound = beg + incre;
            for (sort_element_t * i = bound; i < end; ++i)
            {
                sort_element_t * p = i;
                sort_element_t val = *i;
                for (; p >= bound && val < *(p - incre); p -= incre)
                    *p = *(p - incre);
                *p = val;
            }
        }
        insert_sort(beg, end);
    }
}

这个能理解吧，步长1的时候完全就是插入排序，但真正厉害的在下面这步，要注意到这种写法在变为步长1之前，它的步长是4，我们可以证明整个数组的最小值一定在前4个数中，即前一个步长的范围内。这里不给出具体证明，有兴趣你可以自己试试证明。有了这个结论，前4个元素用插入排序排好了后，后面的就可以使用unguarded_insert_sort了

void shell_sort_o2(sort_element_t * beg, sort_element_t * end)
{
    if (end - beg > 10)
    {
        size_t incre = 1;
        while (incre < (size_t)(end - beg - 1) / 3)
            incre = incre * 3 + 1; // A003462, Pratt, 1971, Knuth, 1973
        for (; incre > 1; incre /= 3)
        {
            sort_element_t * bound = beg + incre;
            for (sort_element_t * i = bound; i < end; ++i)
            {
                sort_element_t * p = i;
                sort_element_t val = *i;
                for (; p >= bound && val < *(p - incre); p -= incre)
                    *p = *(p - incre);
                *p = val;
            }
        }
        insert_sort(beg, beg + 4);
        unguarded_insert_sort(beg + 4, end);
    }
    else
    {
        insert_sort(beg, end);
    }
}

这个哨兵技巧在其它的排序里面甚至别的问题里同样也会存在。除了这个还有没有别的优化空间呢？例如，shellsort的最优情况下的时间复杂度还是O(nlogn)，那有没有办法使得最优情况时间复杂度下降到O(n)呢？确实有办法，如果在某一轮发现没有数进行交换，那么就立即转成带次数限制的插入排序进行尝试，具体请参阅我的sort项目。

测试结果

以下是在 VS2015 上对 4,500,000 个int排序的测试

其中bao_shell是我在sort项目中写的希尔排序，使用了更优的步长序列，里面包含更多的优化技巧，本篇就不一一介绍了。