個(gè)人主頁(yè)：https://chengang.plus/

文章將會(huì)同步到個(gè)人微信公眾號(hào)：Android部落格

1.1 描述

希爾排序在數(shù)組中采用跳躍式分組的策略，通過(guò)某個(gè)增量將數(shù)組元素劃分為若干組，然后分組進(jìn)行插入排序，隨后逐步縮小增量，繼續(xù)按組進(jìn)行插入排序操作，直至增量為1。

希爾排序通過(guò)這種策略使得整個(gè)數(shù)組在初始階段達(dá)到從宏觀(guān)上看基本有序，小的基本在前，大的基本在后。然后縮小增量，到增量為1時(shí)，其實(shí)多數(shù)情況下只需微調(diào)即可，不會(huì)涉及過(guò)多的數(shù)據(jù)移動(dòng)。

我們來(lái)看下希爾排序的基本步驟，在此我們選擇增量gap=length/2，縮小增量繼續(xù)以gap = gap/2的方式，這種增量選擇我們可以用一個(gè)序列來(lái)表示，{n/2,(n/2)/2...1}，稱(chēng)為增量序列。

1.2 代碼

public static void shellInsertSort() {
    int size = number.length;
    int delta = size;
    while (true) {
        delta = delta / 2;
        for (int i = 0; i < delta; i++) {
            Log.d(TAG, "delta is " + delta + " , i = " + i);
            for (int j = i + delta; j < size; j += delta) {
                int tempData = number[j];
                int k = j - delta;
                while (k >= 0 && number[k] > tempData) {
                    number[k + delta] = number[k];
                    k -= delta;
                }
                number[k + delta] = tempData;
            }
        }
        if (delta == 1) {
            break;
        }
    }
    Log.d(TAG, "sorted number is " + Arrays.toString(number));
}

1.3 總結(jié)

• 最外層的循環(huán)被delta控制，當(dāng)分組間隔為1時(shí)，就可以跳出了；
• 第二層循環(huán)其實(shí)確定了分組的界限，第一次在數(shù)組的中間，然后不斷往左偏移；
• 第三層循環(huán)在第二層循環(huán)的基礎(chǔ)上往后偏移一個(gè)delta位置，同時(shí)記住這個(gè)位置的值到tempData變量，同時(shí)記住開(kāi)始與它比較的初始位置，每次都是j后面的一個(gè)偏移delta的位置k；
• 最后一層就是每次不斷往左邊偏移delta，并將偏移的位置與j位置的值比較。

如下圖所示，開(kāi)始delta等于4，后續(xù)每間隔4個(gè)元素做比較，從后往前比較。

• 第二行中8與3比較；7與3比較，只要比3大，8挪到3的位置，7挪到8的位置，最后跳出while循環(huán)，3挪到7的位置。這樣前四行完成了delta為4的循環(huán)；
• 5，6行完成了delta等于2的循環(huán)；
• 剩下的完成了delta等于1的循環(huán)。

希爾排序.jpg