算法-希尔排序

基本思想

希尔排序是在插入排序的基础上的一个改进。

首先它把较大的数据集合分割成若干个小组（逻辑上分组），然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高。

如果有不懂得可以看这篇优质文章讲解

实现

void shellSortCore(vector<int>& nums, int gap, int i)
{
    int inserted = nums[i];
    for(auto j = i - gap;j >=0 && inserted < arr[j];i-=gap)
        arr[j+gap] = arr[j];
    arr[j+gap] = inserted;
}
void shellSort(vector<int>& nums) 
{
     for (int gap = nums.size()/2;gap>0;gap/=2) 
     {
        for(auto i = gap;i<nums.size();++i)
            shellSortCore(nums,gap,i);
    }
}