当前位置: 首页 > news >正文

最新陕西省人事任免优化营商环境条例

最新陕西省人事任免,优化营商环境条例,手机网站源码 php,杭州网站如何制作🥦前言: 希尔排序也称 “缩小增量排序”,它也是一种插入类排序的方法,在学习希尔排序之前我们首先了解一下直接插入排序. 一: 🚩直接插入排序 1.1 🌟排序思路 直接插入排序的基本原理是将一条记录插入到已排好的有序表中&#x…

🥦前言:

        希尔排序也称 “缩小增量排序”,它也是一种插入类排序的方法,在学习希尔排序之前我们首先了解一下直接插入排序.

一: 🚩直接插入排序

1.1 🌟排序思路

        直接插入排序的基本原理是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表,其思路就和我们摸扑克牌一样,每摸到一张牌按照大小把他插入到对应位置,这样等摸完全部的牌时,我们手里的牌就是有序的

动态图解:

        首先我们把数组的第一个元素看作有序的,将第二个元素插入到与第一个元素对应的位置,再将数组的第三个元素插入到相对于数组前两个元素对应的位置,直到最后一个元素插入到对应位置 

代码演示: (排升序)

void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;//首先保存一下待插入的元素int tmp = a[end + 1];//比较的最坏情况时end=0while (end >= 0){//若待排序元素比a[end]小,则让a[end]向后移动腾位置if (tmp < a[end]){a[end + 1] = a[end];end--;}else{//由于本来数组就为有序数组,当不满足上述条件时,说明找到了待插入的位置break;}}//插入数据a[end + 1] = tmp;}
}

1.2 💬直接插入排序特点

  • 直接插入排序的时间复杂度为O(N^2),若待排序表为有序的则时间复杂度为O(N)
  • 待排序表越接近有序则时间复杂度越小
  • 空间复杂度为O(1),是一个稳定的排序算法
  • 与同为时间复杂度为O(N^2)的冒泡排序相比,若待排序数组为有序的,虽然冒泡排序不需要挪动数据,但是其时间复杂度依旧为O(N^2),所以直接插入排序在特定情况下还是优于冒泡排序的

二: 🚩希尔排序

2.1 🌟排序思路

  1. 预排序:先将数组分组,将每个组排序,目的是让整个数组相对有序
  2. 插入排序:待数组相对有序后,进行直接插入排序,这样效率比较高

图解:

假设待排序数组为[9 8 7 6 5 4 3 2 1]

1.我们将他们每隔三个坐标分为一组,假设gap=3

2.对三个数组分别进行直接插入排序,使数组整体相对有序

3.对数组整体进行插入排序


对于代码的理解我们一步一步来

首先我们先理解对红色的一组进行预排序

//希尔排序
void ShellSort(int* a, int n)
{int gap = 3;//要注意i的范围要控制到n-gap以内,因为当end大于等于n-gap时,tmp会越界             for (int i = 0; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}

要对红蓝绿三组都进行排序的话,直接在外层套个循环即可,我们会发现定义gap为几最后数组就会被分割为几组

//希尔排序
void ShellSort(int* a, int n)
{int gap = 3;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

上述代码是排完一组在排一组,其实也可以直接一次性把三组数据全部排好

//希尔排序
void ShellSort(int* a, int n)
{int gap = 3;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}

到了这里数组就预排好了,但是我们得思考一个问题:

        由于我们排序的数组的长度都是不固定的,那直接把gap定死就是不合适的,gap越大,较大的数就能更快的排到后面,gap越小预排出来的数组就越接近有序,当gap=1时就为直接插入排序,所以gap应该随n的大小而变化,并且gap最后应该为1.

        对于希尔增量到底怎么取也没有一个最优的值刚开始有人认为gap=gap/2,但是后来有人认为这样处理预排出来数组还是不够有序,后来又提出了gap=gap/3+1 ,  (+1)是为了确保gap最终能变为1

希尔排序完整代码:

void ShellSort(int* a, int n)
{//首先将gap定为nint gap = n;/*while (gap > 1){gap = gap / 3 + 1;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}*/while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

2.2 💬希尔排序特点

  • 希尔排序其实是对直接插入排序的优化,其效率更高
  • 当gap>1时,为预排序目的是让数组相对有序,当gap=1时,为直接插入排序,目的是让数组有序
  • 希尔排序的时间复杂度不容易计算,但是有专业人士算出希尔排序的时间按复杂度大概为O(N^1.3)
http://www.hrbkazy.com/news/18509.html

相关文章:

  • 做H5哪个网站字体漂亮一些做竞价推广这个工作怎么样
  • 做购物网站用服务器快速排名软件seo系统
  • 网站降权表现seo搜索引擎优化名词解释
  • 中信建设有限公司简介培训班线上优化
  • 章丘网站定制搜索图片识别出处百度识图
  • 专门做视频的网站有哪些营销型网站案例
  • dreamwearver做网站地图做网站的公司哪家好
  • 北京市住房和城乡建设管理委员会网站新一轮疫情最新消息
  • 白云外贸型网站建设百度推广开户流程
  • 手机端网站如何做樱桃磁力bt天堂
  • 用于公司网站建设的费用记帐分录成品app直播源码有什么用
  • 成都网站建设3六六南宁百度seo软件
  • wordpress 正在例行维护济南网站seo
  • 本地网站建设公司广州30万人感染
  • 厦门建网站网址下载app
  • ps做图 游戏下载网站有哪些内容怎么弄自己的网站
  • 建设网贷网站关键词优化到首页怎么做到的
  • 做网站必须要切图吗百度seo推广计划类型包含
  • www 上海网站建设seo优化好做吗
  • 用vs2010做免费网站模板下载地址详情页页面页面
  • 大连建设网站制作百度开户返点
  • pyhton做网站郑州网站运营
  • 做婚恋网站挣钱吗免费个人自助建站
  • WordPress怎么文章分类广东seo推广费用
  • 海口免费网站建设广州百度网站排名优化
  • 东莞虎门南栅医院广州seo公司排行
  • 网站互动化网络营销的概念和特征
  • 教育机构电商网站建设加盟一个万能的营销方案
  • 广东网络公司网站建设关键词检索
  • 动态手机网站怎么做网络搜索引擎有哪些