iOS - 希尔排序
图片源于网络
希尔排序
希尔排序(Shell Sort)又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。该方法因DL．Shell于1959年提出而得名。
算法思想
-
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序
-
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（增量序列的最后一个增量值必须等于1）
-
按增量序列个数k，对序列进行k 趟排序；
-
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
-
仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
图-希尔排序示例图
在上面这幅图中：
-
初始时，有一个大小为 10 的无序序列。
-
在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。 接下来，按照直接插入排序的方法对每个组进行排序。
-
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。按照直接插入排序的方法对每个组进行排序。
-
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
范例代码
/**
希尔排序
@param array 需要排序的Array
*/
+(void)shellSort:(NSMutableArray *)array
{
//希尔排序的思想: 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
//起始间隔值gap设置为总数的一半，
int gap = (int)[array count] / 2;
//当 gap==1 时 结束循环
while (gap >= 1) {
// 把距离为 gap 的元素编为一个组，扫描所有组
for(int i = gap ; i < [array count]; i++){
//取出第gap的数据
int j = i;
NSNumber *temp = array[i];
// 对距离为 gap 的元素组进行排序
while (j >= gap && [temp integerValue] < [array[(j - gap)] integerValue]) {
[array replaceObjectAtIndex:j withObject:array[(j - gap)]];
j = j - gap;
[array replaceObjectAtIndex:j withObject:temp];
}
}
gap = gap / 2;
NSLog(@"希尔排序结果：%@", array);
}
}
算法分析
希尔排序的算法性能
希尔排序的算法性能
时间复杂度
希尔排序的时间复杂度与增量(即，步长gap)的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)，而Hibbard增量的希尔排序的时间复杂度为O(N3/2)。
- Hibbard增量
Hibbard增量的递推公式为：H1 = 1，Hi = 2 * Hi-1 + 1……
初始增量的确定跟排序的趟数有关，我们用t代表趟数，t = log2(n+1)，有小数就取整，想知道第n个增量，则公式为：
第n个增量 = 2(t-n+1) - 1 ，同样也是有小数就取整。
空间复杂度
我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 O(1) 。
算法稳定性
如图图-希尔排序示例图 中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。所以，希尔排序是不稳定的算法。
直接插入排序和希尔排序的比较
-
直接插入排序是稳定的；而希尔排序是不稳定的。
-
直接插入排序更适合于原始记录基本有序的集合。
-
希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
-
在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。
-
直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。
