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;
            }
        }
    }
}

人已赞赏
IOS

IOS 懒加载类和非懒加载类 区别【详解】

2020-10-22 18:29:35

IOS

IOS开发算法 快速排序 【附代码】

2020-10-23 11:21:10

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
'); })();