iOS 希尔排序

  希尔排序(Shell Sort)又称递减增量排序，本质上是插入排序，可以把序列看成一个矩阵，按照步长分成步长m列，逐列进行排序。m按照步长队列依次减小，直至步长为1。
  希尔排序按步长排序一次可以有效减少一些逆序对。希尔本人给出的步长数组为n/(2^k)。比如n = 15 时，步长序列为[8 ，4 ， 2 ， 1]

第一步：构建步长队列

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

第二步：根据每次的步长对每列数组排序

- (void)sortByStep:(NSInteger)step
{
    if (step <= 0) {
        return;
    }
    for (NSInteger col = 0; col < step; col++) { // 划分插入排序的数组
        
        // 对新数组插入排序
        for (NSInteger begain = col + step; begain < self.sortArray.count; begain += step) { // 遍历新数组
            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]];
    }
}

优化点：随着算法的发展，科学家发现了一种更加好的步长队列，可以进一步优化希尔排序的排序速度。[1,5,19,41,109....]

希尔排序的最佳步长队列的数学表达式