希尔排序

算法学习记录-排序——希尔排序 - 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

來源：简书

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