希尔排序-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

希尔排序

简介: 希尔排序

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;

        }

}


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

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章