iOS-希尔排序 iOS-希尔排序

序言以下内容摘自百度百科希尔排序
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
在这之前冒泡、选择、插入排序的时间复杂度基本都是O(n2)的，希尔排序算法是突破这个时间复杂度的第一批算法之一。

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

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

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

基本思想先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 该方法实质上是一种分组插入方法
一般的初次取序列的一半为增量，以后每次减半，直到增量为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(n2),而使用最优的增量在最坏的情况下却为O(n2?3)。需要注意的是，增量序列的最后一个增量值必须等于1才行。另外由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。
本文参考 iOS算法总结-希尔排序
项目链接地址 - ShellSortDemo