#include <bits/stdc++.h>
using namespace std;

//希尔排序
//插入排序的优化版 优化了交换数值的过程
//定义一个总长度 / 2的步长 并不断地折半他
//以步长为长度在数组中进行插入排序

vector<int> nums = {1, 2, 3, 5, 6, 3, 2, 4, 6, 8};

void print(vector<int> num)
{
    for (vector<int>::iterator it = num.begin(); it != num.end(); it++)
    {
        cout << *it << " ";
    }
}

void shell_sort(vector<int> num, int n)
{
    int i = 0;
    int j = 0;
    int temp = 0;

    for (int step = n; step > 0; step = step / 2) //步长公式
    {
        for (i = step; i < n; i++) //从步长开始
        {
            temp = num[i];
            for (j = i; j > step && temp < num[j - step]; j -= step)
            {
                num[j] = num[j - step];
            }
            num[j] = temp;
        }
    }
    print(num);
}

int main()
{
    shell_sort(nums, nums.size());
    return 0;
}