IOS开发算法 希尔排序 【附代码】

今天爱分享给大家带来IOS开发算法 希尔排序 【附代码】，希望能够帮助到大家。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。`
增量： 插入排序只能与相邻的元素进行比较，而希尔排序则是进行跳跃比较，而增量就是步长。
最优的增量在最坏的情况下却为O(n²⁄³)，最坏的情况下时间复杂度仍为O(n²)
需要注意的是，增量序列的最后一个增量值必须等于1才行
另外由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法

- (void)shellSortArray:(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] integerValue]<[array[j-increment] integerValue]) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j-increment];
                j-=increment;
            }
        }
    }
}