原博客：白话经典算法系列之八 MoreWindows白话经典算法之七大排序总结篇

//最佳步长：https://zh.wikipedia.org/wiki/希尔排序

#include <iostream>
#include <vector>
using namespace std;

void shellsort(vector<int> &vi){
    if(vi.size()<=1) return ;
    int n=vi.size();
    for(int step=n/2;step>0;step/=2){
        for(int i=0;i<step;++i){//1
            for(int j=i+step;j<n;j+=step){//2
                //在当前层做插入排序，相当于直接插入排序的第一种优化。见直接插入排序。
                if(vi[j]<vi[j-step]){//如果前一元素大于当前的元素
                    int temp=vi[j];
                    int k=j-step;
                    while(k>=0 && vi[k]>temp){
                        vi[k+step]=vi[k];
                        k=k-step;
                    }
                    vi[k+step]=temp;
                }
            }
        }
    }
}
//优化1：结构上的优化，shellsort中1与2处的for可以合并一下。
void shellsort1(vector<int> &vi){
    if(vi.size()<=1) return ;
    int n=vi.size();
    for(int step=n/2;step>0;step/=2){
        for(int j=step;j<n;++j){
            if(vi[j]<vi[j-step]){
                int temp=vi[j];
                int k=j-step;
                while(k>=0 && vi[k]>temp){
                    vi[k+step]=vi[k];
                    k=k-step;
                }
                vi[k+step]=temp;
            }
        }
    }
}
//优化2：结构上的优化，用swap来使代码更精简，但是效率会变低一点
void shellsort2(vector<int> &vi){
    if(vi.size()<=1) return ;
    int n=vi.size();
    for(int step=n/2;step>0;step/=2)
        for(int j=step;j<n;++j)
            for(int k=j-step;k>=0 && vi[k]>vi[k+step];k-=step)
                swap(vi[k],vi[k+step]);
}

int main(){
    vector<int> vi;
    vi={1,8,2,3,7,6,9,5,4};
//    shellsort(vi);
//    shellsort1(vi);
    shellsort2(vi);
    for(auto ieh: vi)
        cout<<ieh<<" ";
    cout<<endl;
    return 0;
}