希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因DL．Shell于1959年提出而得名。

希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時，整個文件恰被分成一組，算法便終止。

由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。

image.png

希爾排序的時間復(fù)雜度的下界是O(n*log2n),與增量序列的選取有關(guān) 最差情況為O（n^2）

百度百科

計(jì)算步長之后間隔步長的兩個數(shù)進(jìn)行比較之后排序。

    NSMutableArray *arrSort = [NSMutableArray arrayWithArray:@[@(7), @(3), @(15), @(5), @(11), @(2), @(4), @(9), @(6)]];
    [self shellsort:arrSort];

/**
 希爾排序

 @param arrSort 數(shù)組
 */
- (void)shellsort:(NSMutableArray *)arrSort {
    int i, j, gap, n;
    n = (int)arrSort.count;
    // 循環(huán)出步長
    for (gap = n / 2; gap > 0; gap = gap / 2) {
        for (i = gap; i < n; i++) {
            for (j = i - gap; j >= 0; j = j - gap) {
                if (arrSort[j] > arrSort[j + gap]) {
                    NSNumber *x = arrSort[j];
                    arrSort[j] = arrSort[j + gap];
                    arrSort[j + gap] = x;
                }
            }
        }
    }
}

image.png