希尔排序

希尔排序是插入排序(gap = 1)的升级版，插入排序的gap = n/2，n/4，……

#ifndef _SHELL_SORT_H_
#define _SHELL_SORT_H_

#include <vector>

using std::vector;
using std::swap;

void shellSortCore(vector<int> &nums, int gap, int pos);
void shellSort(vector<int>& nums); 

#endif //_SHELLSORT_H_

#include "shellSort.h"
void shellSort(vector<int>& nums) {
    int n = nums.size();
    for(int gap = n/2; gap > 0; gap /= 2) {
        for(int i = gap; i < n; ++i) {//待插入元素的下标,这里是插入排序	
            int x = nums[i];
            int j;
            for(j = i - gap; j >= 0 && nums[j] > x; j -= gap) {
                nums[j + gap] = nums[j];
            }
            nums[j + gap] = x;
        }
    }
}

希尔排序可以说是插⼊排序的⼀种变种。⽆论是插⼊排序还是冒泡排序，如果数组的最⼤值刚好是在第⼀位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的⼀个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对⽐较花时间了