算法学习记录-排序——希尔排序 - 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
來源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。
网友评论