原理

希爾排序也屬于插入類(lèi)排序算法。希爾排序通過(guò)縮小增量，將待排元素劃分為若干個(gè)子序列，分別對(duì)每個(gè)子序列按照直接插入排序算法進(jìn)行排序。當(dāng)增量為1時(shí)，待排序元素構(gòu)成一個(gè)子序列，對(duì)該序列排序完畢后希爾排序結(jié)束?！?/p>

為了減少數(shù)據(jù)的移動(dòng)次數(shù)，在初始序列較大時(shí)取較大的步長(zhǎng)，通常取序列長(zhǎng)度的一半，此時(shí)只有兩個(gè)元素比較，交換一次；之后步長(zhǎng)依次減半直至步長(zhǎng)為1，即為插入排序，由于此時(shí)序列已接近有序，故插入元素時(shí)數(shù)據(jù)移動(dòng)的次數(shù)會(huì)相對(duì)較少，效率得到了提高。

/**
 * shell排序
 * @param a
 * @return
 */
public static int[] shellSort(int[] a){
    int N = a.length;
    int h = 1;
    // 增量序列
    while(h < N/3){
        // h = 1,4,13,40,……
        h = h*3 + 1; 
    }

    while(h>=1){
        for (int i = h; i < N; i++) {
            // 進(jìn)行插入排序，諾a[j]比a[j-h]小，則向前挪動(dòng)h
            for (int j = i; j >= h && a[j-h]>a[j]; j -= h) {
                exc(a, j, j-h);
            }
        }
        h /= 3;
    }
    return a;
}

希爾排序的理念和梳排序的理念有點(diǎn)類(lèi)似。在梳排序中，我們比較距離相差為step的兩個(gè)元素來(lái)完成交換。在希爾排序中，我們的做法也是類(lèi)似。我們?cè)跀?shù)組中每隔h取出數(shù)組中的元素，然后進(jìn)行插入排序。當(dāng)h=1時(shí)，則就是前面所寫(xiě)的插入排序了。

實(shí)例

流程圖

時(shí)間復(fù)雜度：通常認(rèn)為是O(N3/2) ，未驗(yàn)證　　穩(wěn)定性：不穩(wěn)定