??希爾排序(Shell Sort)又稱遞減增量排序，本質(zhì)上是插入排序，可以把序列看成一個矩陣，按照步長分成步長m列，逐列進(jìn)行排序。m按照步長隊(duì)列依次減小，直至步長為1。
??希爾排序按步長排序一次可以有效減少一些逆序?qū)ΑＯ柋救私o出的步長數(shù)組為n/(2^k)。比如n = 15 時，步長序列為[8 ，4 ， 2 ， 1]

第一步：構(gòu)建步長隊(duì)列

- (void)creatStepQueue
{
    [self.stepQueue removeAllObjects];
    NSInteger count = self.sortArray.count;
    while ((count /= 2) > 0) {
        [self.stepQueue addObject:@(count)];
    }
    NSLog(@"stepArray = %@",self.stepQueue);
}

第二步：根據(jù)每次的步長對每列數(shù)組排序

- (void)sortByStep:(NSInteger)step
{
    if (step <= 0) {
        return;
    }
    for (NSInteger col = 0; col < step; col++) { // 劃分插入排序的數(shù)組
        
        // 對新數(shù)組插入排序
        for (NSInteger begain = col + step; begain < self.sortArray.count; begain += step) { // 遍歷新數(shù)組
            NSInteger currtent = begain;
            while (currtent > col && [self compareObjcet:self.sortArray[currtent] anotherObject:self.sortArray[currtent - step]]) {
                [self swapObjectWithIndex:currtent anotherIndex:currtent - step];
                currtent -= step;
            }
            
        }
    }
}

那么整體的排序過程

- (void)sort
{
    [self creatStepQueue];
    
    for (NSNumber *step in self.stepQueue) {
        [self sortByStep:[step integerValue]];
    }
}

優(yōu)化點(diǎn)：隨著算法的發(fā)展，科學(xué)家發(fā)現(xiàn)了一種更加好的步長隊(duì)列，可以進(jìn)一步優(yōu)化希爾排序的排序速度。[1,5,19,41,109....]

希爾排序的最佳步長隊(duì)列的數(shù)學(xué)表達(dá)式