希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

image.png

希尔排序的时间复杂度的下界是O(n*log2n),与增量序列的选取有关 最差情况为O（n^2）

百度百科

计算步长之后间隔步长的两个数进行比较之后排序。

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

/**
 希尔排序

 @param arrSort 数组
 */
- (void)shellsort:(NSMutableArray *)arrSort {
    int i, j, gap, n;
    n = (int)arrSort.count;
    // 循环出步长
    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