5.4 希尔排序

简介

也称递减增量排序算法，是插入排序的一种更高效的改进版本。他的思想是：先将整个待排序列的记录序列分割成为若干个子序列分别进行插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

算法步骤

选择一个增量序列 t1 t2 … tk，其中 ti > tj，tk = 1;
按增量序列个数 K，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干个长度为 m 的子序列，分别对各子序列进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

void shellsort(vector<int>& nums) {
    int h = 1;
    while (h < nums.size() / 3) {
        h = h * 3 + 1;
    }
    while (h >= 1) {
        for (int i = h; i < nums.size(); ++i) {
            for (int j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
                swap(nums[j], nums[j - h]);
            }
        }
        h /= 3;
    }
}