iOS-希尔排序

序言

以下内容摘自百度百科 希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

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

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

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 1 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
• 2 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

基本思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量，即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入方法
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

给定实例的shell排序的排序过程

假设待排序文件有10个记录，其关键字分别是：

49，38，65，97，76，13，27，49，55，04。

增量 依次取值为 5，2，1

image.png

解释说明
希尔排序在插入排序的基础上增加一个叫增量的概念。那什么增量？插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。比如增量为5时，下标为0的元素与下标为5的元素比较，5再与10比较，1与6比较，6再与11比较……比较完后，再去减少增量，重复之前步骤，直到增量为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;
            
            // 以下就是一个直接插入比较算法,只是直接插入比较的增量为1,希尔排序的增量为gap罢了
            // j >= gap 因为增量为gap,所以只有当j >= 增量时,才有必要进行比较
            // [j - gap] 因为gap为增量,每次都是以增量为跨度进行比较的
            while (j >= gap && temp < [[list objectAtIndex:(j - gap)] intValue]) {
                // 将比较大的数据移动到j位置上
                [list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-gap]];
                // 往前移动增量个数,进行比较
                j -= gap;
            }
            // 将待排序值插入j位置上
            [list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
        }
        NSLog(@"%@",[self getArrayStr:list]);
        gap = gap / 2;
    }
}

// 将数组中的元素拼接成字符串 - 方便打印
- (NSString *)getArrayStr:(NSArray *)array {
    NSMutableString *strM = [NSMutableString string];
    for (NSNumber *num in array) {
        [strM appendString:[NSString stringWithFormat:@"%@,",num]];
    }
    return strM.copy;
}

将待排序的数组进行希尔排序

NSArray *array = @[@3,@2, @6, @9, @8, @5, @7, @1, @4];
[self shellSort:[NSMutableArray arrayWithArray:array]];

运行结果

image.png

算法详细画图分解：

image.png

增量的说明

因为增量的选择是希尔排序的重要部分, 所以摘出来单独说明。

已知的最好增量序列是由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，...

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

稳定性

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

时间性能

• 1 增量序列的选择

Shell排序的执行时间依赖于增量序列。

好的增量序列的共同特征：

• 最后一个增量必须为1；
• 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

有人通过大量的实验，给出了较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。

• 2 Shell排序的时间性能优于直接插入排序

希尔排序的时间性能优于直接插入排序的原因

• 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
• 当n值较小时，n和 n * n 的差别也较小，即直接插入排序的最好[时间复杂度]O(n)和最坏时间复杂度0(n*n)差别不大。
• 在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

因此，希尔排序在效率上较直接插入排序有较大的改进。

希尔排序复杂度分析：

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

---

本文参考 iOS算法总结-希尔排序

---

项目链接地址 - ShellSortDemo