开发者社区> ggbond233> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

希尔排序

简介: 希尔排序
+关注继续查看

shellSort

https://www.cnblogs.com/chengxiao/p/6104371.html

希尔排序,也称缩小增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。同时该算法是冲破O(n^2)的第一批算法之一,希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ,因此对中等大小规模表现良好,但对规模非常大的数据排序不是最优选择,总之比一般 O(n^2 ) 复杂度的算法快得多

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
  • 但插入排序一般来说是低效的,因为插入排序每次比较后只能将数据移动一个位置

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

  1. 外层循环控制间隔的缩小,间隔gap初始为n/2,每次二分直到为1,排序完成
  2. 内层循环就是间隔为gap的插入排序,把插入排序的第二层循环中的1全部换成gap即可

算法步骤

template <typename T>

void shellSort(T arr[],int n){

    for(int gap=n/2;gap>0;gap/=2){

        //希尔排序内部循环是插入排序,插入排序增量为1,希尔排序增量由外层循环控制

        //从第gap个元素,进行插入排序

        for(int i=gap;i<n;i++){

            T e=arr[i];

            int j;

            //对第一组的部分元素进行排序

            //希尔排序每次移动为gap,即间隔为gap

            for(j=i;j-gap>=0;j=j-gap){

                if(e<arr[j-gap])//往后移增量个

                    arr[j]=arr[j-gap];

                else break;

            }

            arr[j]=e;

        }

    }

}

template <typename T>

void shellSort(T arr[],int n){

    //缩小增量直到1

    for(int gap=n/2;gap>0;gap/=2)

        //从第gap个元素,逐个对其所在组进行直接插入排序操作

        for(int i=gap;i<n;i++){

            int j=i;

            int temp=arr[i];

            //与前面的元素进行比较

            while(j-gap>=0&&arr[j-gap]>temp){

                arr[j]=arr[j-gap];

                j-=gap;

            }

            arr[j]=temp;

        }

}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
C#——希尔排序
C#——希尔排序
0 0
插入排序 ( 直接插入排序 && 希尔排序 )
插入排序 ( 直接插入排序 && 希尔排序 )
0 0
希尔排序就这么简单
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
0 0
希尔排序_C++
是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
845 0
【26】希尔排序
参考高爽的博客http://hi.baidu.com/gsgaoshuang/item/17a8ed3c24d9b1ba134b14c2 1. 希尔排序又称为缩小增量排序,属于插入排序算法的改进。
730 0
C# 希尔排序
点击打开链接 作者:jiankunking 出处:http://blog.csdn.net/jiankunking
421 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载