尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
数据结构:选择排序
上一篇我们讲了插入排序这一篇我们来讲选择排序。因为堆排序之前我们有详细讲过所以这里只给出堆排序的思路有兴趣的可以看一看。选择排序选择排序就是从数组中选出最小值和最大值最小值放在第一个位置最大值放在最后一个位置依次执行直到排成有序数组为止。直接选择排序直接选择排序就是从begin到end范围中获取最大值和最小值将最小值放到begin位置最大值放到end位置。依次执行直到排成有序数组为止。思路比如说我们有以下数组我们把数组起始位置作为begin末尾作为end从中找出最小值mini和最大值maxi。我们将最小值mini位置和begin位置数据交换一下然后将最大值maxi位置和end位置数据交换一下使得最小值放到begin位置最大值放到end位置。然后beginend- -再从beign到end范围中找出最小值mini和最大值maxi。将mini和begin数据交换maxi和end数据交换。然后beginend- -继续从begin到end范围中找最小值和最大值。此时我们发现maxi在begin位置如果我们继续直接交换mini和beginmaxi和end就会发生这样一件事。我们发现最小值没有来到begin位置最大值也没有到end位置这是为什么呢maxi在begin位置的时候我们先交换的是begin和mini位置的数据这会导致maxi被交换到了mini的位置。因此当begin maxi的时候我们要让maxi mini这步的意义是存储begin被交换后maxi当前所处的位置这样end和maxi交换才不会出错。## 代码实现综上所述我们排序的循环条件是begin end当end begin的时候则说明排序结束了。然后初始情况下begin 0end n - 1;每次找到最小值最大值并放到beginend位置后beginend–。接下来我们定义mini和maxi我们让它们一开始等于begin然后从begin 1到end位置遍历一遍找最大值和最小值。因为我们是先将最小值放到begin处所以要判断begin maxi是否成立如果成立则让maxi mini记录交换后最大值的位置。如果我们是先将最大值放到end处则需要判断end mini成立则让mini maxi。然后将mini处数据和begin处交换maxi处数据和end处交换。这个代码就写好了。我们来简单测试一下。结果符合预期说明代码没什么问题。时间复杂度该算法嵌套了两层循环外层因为是两边同时查找循环次数缩短到了 n/2内层循环总次数也相当于一个公差为 -2 的等差数列之和总的来说无论什么情况该算法时间复杂度为 O(n2)。堆排序如果有兴趣的可以看看这篇文章详细内容不再赘述。数据结构:堆排序堆排序是利用堆的思想来进行排序的算法将原数组通过向上/向下调整算法调整成一个大堆然后堆顶和堆底元素数组开头和末尾进行交换数组大小 size–再调整前 size 个元素保证成为一个大堆结构循环往复直到 size 0排序结束。voidSwap(int*x,int*y){inttmp*x;*x*y;*ytmp;}//向下调整算法voidAdjustDown(int*arr,intparent,intn){intchildparent*21;//左孩子while(childn){if(child1narr[child1]arr[child])child;if(arr[parent]arr[child]){Swap(arr[parent],arr[child]);parentchild;childparent*21;}elsebreak;}}//向上调整算法AdjustUp(int*arr,intchild){intparent(child-1)/2;while(child0){if(arr[parent]arr[child]){Swap(arr[parent],arr[child]);childparent;parent(child-1)/2;}elsebreak;}}//堆排序voidHeapSort(int*arr,intn){//建大堆for(inti(n-1-1)/2;i--;i0){AdjustDown(arr,i,n);}//排序while(n0){//交换堆顶和堆底元素Swap(arr[0],arr[n-1]);n--;AdjustDown(arr,0,n);}}
RELATED

相关推荐

3个维修隐坑|东莞笔记本插耳机仍外放自查,80%不用更换声卡

3个维修隐坑|东莞笔记本插耳机仍外放自查,80%不用更换声卡

1. 前言日常办公、网课学习时,笔记本音频异常的情况时有发生。明明耳机已经插紧,机身扬声器依旧持续发声,耳机完全没有音频输出。不少用户分不清软件故障和硬件损坏,直接选择送修。结合东莞本地长期接修的案例来看,这类…

📅 2026/11/17 2:32:46
理解 WebAssembly:它解决什么问题

理解 WebAssembly:它解决什么问题

WebAssembly(简称 Wasm)是一种可在浏览器(以及越来越多其它运行时)里执行的二进制指令格式。它不是用来取代 JavaScript 写页面的,而是给「算得重、又想在 Web 里跑」的那部分逻辑一条更合适的路。 宣传语常说「近原生…

📅 2026/11/15 15:36:50
【中国机械工程学会、西北工业大学主办 | 陕西西安举办】第30届中国机械工程学会工业设计分会学术年会暨第七届智能设计国际会议(ICID 2026)

【中国机械工程学会、西北工业大学主办 | 陕西西安举办】第30届中国机械工程学会工业设计分会学术年会暨第七届智能设计国际会议(ICID 2026)

第30届中国机械工程学会工业设计分会学术年会暨第七届智能设计国际会议(ICID 2026) The 30th Annual Academic Conference of the Industrial Design Branch of the China Mechanical Engineering Society & 2026 7th International Confere…

📅 2026/11/16 23:43:28
MORE NEWS

更多资讯

📰

初级电工证是上岗证吗?上岗必备的备考攻略来了

初级电工证是上岗证吗?上岗必备的备考攻略来了 工地太忙根本没时间复习考试,这话在很多一线电工心里都憋着,尤其是刚从学校或培训学校出来,准备进入工地的新人。初级电工证是不是上岗证?这个问题关系到你能不能顺利上岗,能不能拿到第一份工资。今天咱们…

📰

工地太忙根本没时间复习考试 低压电工证培训心得怎么应对2026河南最新政策

工地太忙根本没时间复习考试 低压电工证培训心得怎么应对2026河南最新政策 工地太忙根本没时间复习考试,尤其是像低压电工证这样的特种作业证,很多一线工人觉得备考压力大、时间紧,加上2026年河南最新政策出台后,考试内容和流程有了调整,很多人…

📰

高配电工证难吗良心建议:考不过白交培训费怎么破

高配电工证难吗良心建议:考不过白交培训费怎么破 怕考不过白交培训费?高配电工证难吗?作为从业10年的应急管理行业老手,我见过太多人因为培训费花了七八千块,结果考试没过,直接放弃,浪费了时间和钱。今天我用最实在的良心建议,告诉你高配电工证到底…

📰

荆州电工证在哪儿培训,全国通用怎么选不被坑

荆州电工证在哪儿培训,全国通用怎么选不被坑 你是不是也和很多人一样, 不知道去哪报名怕被中介坑 ?尤其是像荆州这样的地方,电工证培训信息五花八门,让人眼花缭乱。你可能还在纠结到底该选哪个机构,又怕花冤枉钱还拿不到证,甚至耽误工作。别急,这篇…

📰

石龙电工证打印在哪里 通过率揭秘:别再为考不过白交培训费焦虑了

石龙电工证打印在哪里 通过率揭秘:别再为考不过白交培训费焦虑了 怕考不过白交培训费?你不是一个人,石龙电工证打印在哪里这个问题,直接关系到你能否顺利拿到证书,也影响着你接下来的薪资和职业发展。今天就带你一探究竟, 通过率揭秘…

📰

电工证下证了多久拿到良心建议全流程解析

电工证下证了多久拿到良心建议全流程解析 你是不是也遇到过这种情况?急需特种作业证才能上岗找工作,结果跑了几家培训机构,听得云里雾里,最后连证能不能拿到、多久能拿到都没个准数?别急,这篇【电工证下证了多久拿到】良心建议,就是为你准备的干货,手…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬