希尔排序

作者: 一代骄马 | 来源:发表于2018-09-11 22:07 被阅读50次

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

來源:简书

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

相关文章

  • 排序算法(二)之希尔排序

    图解排序算法(二)之希尔排序 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也...

  • 07-希尔排序(Shell Sort)

    希尔排序(Shell Sort) 希尔排序是唐纳德·希尔(Donald Shell)在0959年提出的。希尔排序与...

  • 排序-希尔排序(分治)

    希尔排序 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序...

  • swift经典算法-希尔排序

    希尔排序 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序...

  • 排序算法④——希尔排序

    希尔排序 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序...

  • 排序算法-希尔排序(Java实现)

    希尔排序 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是...

  • 说说算法那些事-希尔排序

    希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,希尔排序法又称...

  • 希尔排序学习

    希尔排序希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序是基...

  • 排序算法(四) 希尔排序(插入排序的进化)

    参考Java排序算法(四):希尔排序常见排序算法 - 希尔排序 (Shell Sort) 希尔排序算法是按其设计者...

  • 编程马拉松 Day04 希尔排序、归并排序、快速排序

    本文将介绍三个高级排序算法 希尔排序 归并排序 快速排序 希尔排序 希尔排序(Shell's Sort)的名称源于...

网友评论

    本文标题:希尔排序

    本文链接:https://www.haomeiwen.com/subject/khhugftx.html