升序 縮小增量排序基本思想:
選擇一個(gè)增量因子dk(dk=n/2,n是序列數(shù)量),將序列List[n]分割成若干個(gè)小序列,list(0,dk),list(1,dk+1)....list(n-dk+1,n-1)很多小序列的元素下標(biāo)相差dk,對(duì)小序列進(jìn)行直接插入排序，再將原有序列按照增量因子dk=dk/2;將序列分割成若干個(gè)小序列，小序列的元素下標(biāo)相差dk,對(duì)小序列進(jìn)行直接插入排序，直到dk=1；然后對(duì)“基本有序”原有序列，再進(jìn)行直接插入排序。 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;//記錄較大的數(shù)組元素下標(biāo)
            temp = a[i];//記錄數(shù)組較小元素的值
            
            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;
    }
}

希爾排序在最好的情況下的時(shí)間復(fù)雜度是O(n)
在平均的時(shí)間復(fù)雜度是O(n^1.3)
在最壞的情況下的時(shí)間復(fù)雜度是O(n^2)

希爾排序是一個(gè)不穩(wěn)定的排序算法。