05数据结构排序算法之希尔排序

希尔排序（shell sort）基本思想是把数据按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的数据越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。

代码实现：

/**
 *  希尔排序
 *
 *  @param dataArray 要排序的数据源
 *
 *  @return 已排序的数据
 */
+ (NSArray *)shellSort:(NSArray *)dataArray {
    NSMutableArray *resultArray = [NSMutableArray arrayWithArray:dataArray];
    NSInteger increment = resultArray.count;
    NSInteger j;
    do {
        //计算增量 据说这样算出来的增量计算的效率最高
        increment = increment / 2;
        //开始循环
        for (NSInteger i = increment; i < resultArray.count; i ++) {
            //比较增量两端的值，如果不符合顺序要求则进入循环进行排序
            if (resultArray[i] < resultArray[i - increment]) {
                
                //进入这里最少会执行一次循环，执行后在该增量分组内循环判断，确保组内是按照顺序排序
                for (j = i; j - increment >= 0 && resultArray[j] < resultArray[j - increment]; j -= increment) {
                    [resultArray exchangeObjectAtIndex:j withObjectAtIndex:j - increment];
                }
            }
        }
        
    } while (increment > 1);
    return resultArray;
}

简要分析：

希尔排序

刚开始数据分为5组（8，3），（9，5），（1，4），（7，6），（2，0）
分别组内比较，如果不满足从小到大顺序则交换数据位置。
第一轮结束，数组顺序为 3，5，1，6，0，8，9，4，7，2

第二轮增量为2，先比较3和1，满足条件，交换3和1位置，
交换后数组顺序为1，5，3，6，0，8，9，4，7，2
然后比较3和0，满足条件，交换3和0位置
交换后数组顺序为1，5，0，6，3，8，9，4，7，2
然后比较1和0，满足条件，交换1和0位置
交换后数组顺序为0，5，1，6，3，8，9，4，7，2

再然后比较3和9，不满足条件
然后比较9和7，满足条件，交换9和7位置
交换后数组顺序为0，5，1，6，3，8，7，4，9，2
然后比较3和7，不满足条件
到此，第二轮结束

接着缩小增量，进行下一轮