希尔排序

升序 缩小增量排序基本思想:
选择一个增量因子dk(dk=n/2,n是序列数量),将序列List[n]分割成若干个小序列,list(0,dk),list(1,dk+1)....list(n-dk+1,n-1)很多小序列的元素下标相差dk,对小序列进行直接插入排序，再将原有序列按照增量因子dk=dk/2;将序列分割成若干个小序列，小序列的元素下标相差dk,对小序列进行直接插入排序，直到dk=1；然后对“基本有序”原有序列，再进行直接插入排序。 9 8 7 6 5 4 1 2 6

//升序排序
void shellInsertSort(int a[],int n,int dk){
    int j = 0;
    int temp = 0;
    int i = 0;
    for (i = dk ; i< n; i++) {
        
        if (a[i]<a[i-dk]) {
            
            j = i - dk;//记录较大的数组元素下标
            temp = a[i];//记录数组较小元素的值
            
            while (temp <a[j]&&j>=0) {
                
                a[j+dk] =a[j];
                
                j-=dk;
            }
        }
        a[j+dk] =temp;
    }
}

void shellSort(int a[],int n){
    
    int dk = n/2;
    
    while (dk>=1) {
        
        shellInsertSort(a, n, dk);
        
        dk =dk/2;
    }
}

希尔排序在最好的情况下的时间复杂度是O(n)
在平均的时间复杂度是O(n^1.3)
在最坏的情况下的时间复杂度是O(n^2)

希尔排序是一个不稳定的排序算法。