算法学习记录-排序——希尔排序 - sjdang - 博客园
iOS算法总结-希尔排序 - 简书
与插入排序不同，我们不希望它是一步一步的移动，而是大步大步的移动。希尔排序就被发明出来了，它也是当时打破效率
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
來源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。
