iOS/OC:希尔排序的理解

希尔排序(Shell Sort)，一听这名字就知道是一个叫希尔的外国人发明的排序。没错，他就是唐纳德 希尔（Donald Shell），一位美国的计算机科学家，他于1959年发明的希尔排序算法。

对于希尔排序，比较正式的官方的解释是这样：

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

希尔排序也是插入排序的一种。既然是其中的一种，那么他们的区别是什么呢？插入排序在最坏的情况下，即整个数组是倒序的，此时时间复杂度达到了O(n²)。希尔排序在插入排序的基础上增加一个叫增量的概念。那什么增量？插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。比如增量为3时，下标为0的元素与下标为3的元素比较，3再与6比较，1与4比较，4再与7比较……想必你肯定做过一群人站成一排，按一二报数，喊一的一队，喊二的一队，此时的增量就是2。所以你也可以理解为是按增量进行了分组，再对每一组进行插入排序。当使用一个增量对所有的分组排好序后，再去减少增量，重复之前步骤，直到增量为1，此时只有一个分组了，再对这一个分组进行插入排序，整个希尔排序就结束了（所以希尔排序也叫缩小增量排序，但显然没有希尔排序好听和高大上 斜眼笑）。

从增量的初始值选取，到逐渐变为1，将所有用过的增量组成一个序列，就是增量序列。而希尔排序的增量序列选择直接影响它的时间复杂度（不要问我为什么，我也不知道）。最简单的增量就是希尔鼓励使用的希尔增量。增量初始值选择为N/2（N为数组长度），然后每次将增量除以2，得到下一个增量。所以它的增量序列为{N/2, (N / 2)/2, ..., 1}。除了希尔增量还有Hibbard 增量、Knuth增量等等都是很复杂的数学公式，我怕你看了晕，就放在后面介绍吧！（说的好像自己看了不晕一样）

那下面我们就以最简单的希尔增量来进行希尔排序。

 void shellSort (NSMutableArray *array) {
  int count = (int)array.count;
  //初始增量为数组长度的一半，然后每次除以2取整
  for (int increment = count/2; increment>0; increment /=2) {
  //初始下标设为第一个增量的位置，然后递增
    for (int i = increment; i<count; i++) {
        //获取当前位置
        int j = i;
        //然后将此位置之前的元素，按照增量进行跳跃式比较
        while (j-increment>=0 && array[j]<array[j-increment]) {
            [array exchangeObjectAtIndex:j withObjectAtIndex:j-increment];
            j-=increment;
        }
    }
  }
}

然后对比之前文章所写的选择排序和插入排序。

void selectorSort (NSMutableArray * array){
  NSInteger count = array.count;
  for (int i = 0; i< count; i++) {
    int minIndex = i;
    for (int j = i + 1; j < count; j++) {
        if (array[j] < array[minIndex]) {
            minIndex = j;
        }
    }
    [array exchangeObjectAtIndex:i withObjectAtIndex:minIndex];
  }
}
void insertionSort (NSMutableArray *array) {
  NSInteger count = array.count;
  for (int i = 1; i<count; i++) {
    for (int j = i; j>0; j--) {
        if (array[j] < array[j-1]) {
            [array exchangeObjectAtIndex:j withObjectAtIndex:j-1];
        }else{
            break;
        }
    }
  }
}

三个同样的数组，分别使用选择、插入、希尔进行排序比较时间。

 int main(int argc, const char * argv[]) {
  @autoreleasepool {
    NSMutableArray * sortArray1 = createDifferentArr(20000);
    NSMutableArray * sortArray2 = [sortArray1 mutableCopy];
    NSMutableArray * sortArray3 = [sortArray1 mutableCopy];
    //插入排序
    double startTime1 = CFAbsoluteTimeGetCurrent();
    insertionSort(sortArray1);
    double endTime1 = CFAbsoluteTimeGetCurrent();
    NSLog(@"插入排序用时:%f s",endTime1 - startTime1);
    //选择排序
    double startTime2 = CFAbsoluteTimeGetCurrent();
    selectorSort(sortArray2);
    double endTime2 = CFAbsoluteTimeGetCurrent();
    NSLog(@"选择排序用时:%f s",endTime2 - startTime2);
    //希尔排序
    double startTime3 = CFAbsoluteTimeGetCurrent();
    shellSort(sortArray3);
    double endTime3 = CFAbsoluteTimeGetCurrent();
    NSLog(@"希尔排序用时:%f s",endTime3 - startTime3);
  }
  return 0;
}

数组长度1万时打印结果为：

2017-07-12 14:14:22.484 排序比较[14883:1166946] 插入排序用时:1.848809 s
2017-07-12 14:14:25.161 排序比较[14883:1166946] 选择排序用时:2.675773 s
2017-07-12 14:14:25.179 排序比较[14883:1166946] 希尔排序用时:0.017643 s

数组长度为两万时打印结果为：

2017-07-12 14:15:59.069 排序比较[14899:1169188] 插入排序用时:6.654105 s
2017-07-12 14:16:07.687 排序比较[14899:1169188] 选择排序用时:8.615417 s
2017-07-12 14:16:07.726 排序比较[14899:1169188] 希尔排序用时:0.039497 s

差距是很明显的。

---

希尔排序为不稳定性排序。因为相同的元素可能在各自的插入排序中移动，所以它的稳定性就被打破了。可能有人想问，稳定性是干嘛的啊？稳定的意思是指相同的元素在排序后的相对位置不变。比如有两个5 ，作为区分前面的叫5₁，后面的叫5₂，排序完成后5₁还在5₂的前面。那你可能会问，反正是一样的，换了就换呗。但是在实际应用中被排序的对象会拥有不同的属性，举个栗子，公司在招聘时，想要年龄小的，所以对所有人进行了按年龄的排序。之后还想看成绩分数高的。所以在按成绩进行排序时就有可能出现成绩一样的，但他们的年龄不一样，而你不能把成绩相同但年龄大的排在小的前面。此时算法的稳定性就有了意义。

• 关于hibbard增量
  hibbard增量的递推公式为：H₁ = 1，H_i = 2 * H_i-1 + 1……
  这一看，这是从后往前推倒的啊，那初始增量怎么算啊？
  初始增量的确定跟排序的趟数有关，我们用t代表趟数，t = log₂(n+1)，有小数就取整，想知道第n个增量，则公式为：
  第n个增量 = 2^(t-n+1) - 1 ，同样也是有小数就取整。

使用希尔增量，在最坏的情况下时间复杂度仍为O(n²),而使用hibbard增量在最坏的情况下却为O(n^3/2)。

如果觉得作者对哪里的理解有偏差或者其他的优化，希望不吝赐教，留言指正。谢谢支持~