希尔排序

希尔排序

与插入排序不同，我们不希望它是一步一步的移动，而是大步大步的移动。希尔排序就被发明出来了，它也是当时打破效率

O（n2）的算法之一。希尔排序算法通过设置一个间隔，对同样间隔的数的集合进行插入排序，此数集合中的元素

移位的长度是以间隔的长度为准，这样就实现了大步位移。但是最后需要对元素集合进行一次直接插入排序，所以

最后的间隔一定是1。

下面举一个例子：

第一趟希尔排序，间隔为4

第二趟排序：间隔是2

第三趟间隔为1，即直接插入排序法：

。。。

。。

。

//起始间隔值gap设置为总数的一半，直到gap==1结束

-(void)shellSort:(NSMutableArray *)list{

int gap = (int)list.count /2;

while(gap >=1) {

for( int i = gap ; i < [list count]; i++){

NSInteger temp = [[list objectAtIndex:i] intValue];

int j = i;

while(j >= gap && temp < [[list objectAtIndex:(j - gap)] intValue]) {

[list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-gap]];

j -= gap;

}

[list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];

} gap = gap /2;

}

作者：方圆一里

链接：https://www.jianshu.com/p/c74dd2954b8e

來源：简书

简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。