希尔排序

简介

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本，但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

流程

希尔排序的过程

插入排序的时间复杂度是O（n²），但是如果数据是有序的，插入排序的效率会大幅提升，可以达到O（n）的时间复杂度，所以数据的有序性对插入排序的性能影响较大。

希尔排序也是采用分治的思想通过多次迭代将数据变得相对有序，从而减少插入排序流程中需要比较的次数。

希尔排序会将数字进行多次分组，分组会从小到大依此进行，例如第一次分组是将元素分为两个一组，因为插入排序在小数据量时有较好的效率，之后，分组会逐渐变大，到4个一组，8个一组，直到n/2个一组，数据量较大时候，插入排序的性能会有所下降，但是因为之前的分组使得数据变得相对有序，会提高后续插入排序的效率。

比如10个数字的希尔排序。

第一次把数据分为分组，10除以2得出分为5组，之后对5组数据分别进行插入排序。

第二次把数据分为2组，10除以4得出，之后对这两组数据进行插入排序。

以此类推，第n次分组的组数为元素个数/2ⁿ，直到仅剩下一个分组，进行一轮完整的插入排序。

插入排序进行分组不是简单的逐段分割，而是跳跃式的分组，该分组方式可以使得数据相对有序，而且中间会有一定的插入空间，从而减少插入时候的移动数量。

源码

#include<iostream>
#include<vector>
using namespace std;
void ShellSort(vector<int>vec)
{
        // 希尔排序
    for(int gap=vec.size()/2;gap>0;gap/=2)
    {
                // 直接插入排序
        for(int i=gap;i<vec.size();++i)
        {
            int j=i;
            while(j-gap>=0 && vec[j-gap]>vec[j])
            {
                vec[j-gap] = vec[j-gap]+vec[j];
                vec[j]     = vec[j-gap]-vec[j];
                vec[j-gap] = vec[j-gap]-vec[j];
                j=j-gap;
            }
        }
    }
         
        // 打印输出
    for(int i=0;i<vec.size();++i)
    {
        cout<<vec[i]<<endl;
    }
 
}
int main()
{
    vector<int> vec={8,9,1,7,2,3,5,4,6,0};
    ShellSort(vec);
    return 0;
}