iOS算法总结-希尔排序

希尔排序(Shell Sort)：是插入排序算法的一种更高效的改进版本。在这之前冒泡、选择、插入排序的时间复杂度基本都是O(n²)的，希尔排序算法是突破这个时间复杂度的第一批算法之一。

官方解释如下：

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

希尔排序在插入排序的基础上增加一个叫增量的概念。那什么增量？插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。比如增量为3时，下标为0的元素与下标为3的元素比较，3再与6比较，1与4比较，4再与7比较……比较完后，再去减少增量，重复之前步骤，直到增量为1，此时只有一个分组了，再对这一个分组进行插入排序，整个希尔排序就结束了。

代码如下：

//起始间隔值gap设置为总数的一半，直到gap==1结束
-(void)shellSort:(NSMutableArray *)list{
    int gap = (int)list.count / 2;
    while (gap >= 1) {
        for(int i = gap ; i < [list count]; i++){
            NSInteger temp = [[list objectAtIndex:i] intValue];
            int j = i;
            while (j >= gap && temp < [[list objectAtIndex:(j - gap)] intValue]) {
                [list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-gap]];
                j -= gap;
            }
            [list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
        }
        gap = gap / 2;
    }
}

// 传入@[@8,@7,@6,@5,@4,@3,@2,@1]，表变化如下：
8 7 6 5 8 3 2 1
4 7 6 5 8 3 2 1
4 7 6 5 8 7 2 1
4 3 6 5 8 7 2 1
4 3 6 5 8 7 6 1
4 3 2 5 8 7 6 1
4 3 2 5 8 7 6 5
4 3 2 1 8 7 6 5
4 3 4 1 8 7 6 5
2 3 4 1 8 7 6 5
2 3 4 3 8 7 6 5
2 1 4 3 8 7 6 5
2 1 4 3 6 7 8 5
2 1 4 3 6 7 8 7
2 1 4 3 6 5 8 7
2 2 4 3 6 5 8 7
1 2 4 3 6 5 8 7
1 2 4 4 6 5 8 7
1 2 3 4 6 5 8 7
1 2 3 4 6 6 8 7
1 2 3 4 5 6 8 7
1 2 3 4 5 6 8 8
1 2 3 4 5 6 7 8

希尔排序示例图如下：

对上图解释如下：

1. 起始增量值设置为总数的2/3。
2. 从增量位置开始，依次与差一个增量的前一个值比较。例：第一个与表总数的2/3的元素比，小的移动到前面。 比较完后起始位置+1继续比较。
3. 比较到最后，增量减半，并以此为起始点， 重复第二步，直到间隔数为1为止结束。

增量的计算

因为增量的选择是希尔排序的重要部分, 所以摘出来单独说明。 作者最初的建议是折半再折半直到最后的增量为1, 但是当用较小增量排序后，以前用的较大增量仍然是有序的。 如果一个数列以增量5进行了排序然后再以增量3进行排序，那么该数列不仅是以增量3有序，而且是以增量5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。

已知的最好增量序列是由Sedgewick提出的 1，5，19，41，109，...

它是由交错两个序列的元素获得：<公式: 9（4 ķ - 2 ķ）+ 1 和 2 K + 2（2 K + 2 - 3）+ 1 >
1，19，109，505，2161，... ...，|| 9（4 ķ - 2 ķ）+ 1，K = 0，1，2，3，... 5，41，209，929，3905，... ..|| 2 K + 2（2 K + 2 - 3）+ 1，K = 0，1，2，3，...

用这样增量序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

希尔排序复杂度分析：

在最坏的情况下时间复杂度仍为O(n²),而使用最优的增量在最坏的情况下却为O(n²⁄³)。需要注意的是，增量序列的最后一个增量值必须等于1才行。另外由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。

上一篇：iOS算法总结-插入排序
下一篇：iOS算法总结-堆排序