热点评!各种常见排序算法实现 常见排序算法汇总
各种常见排序算法实现
(资料图片仅供参考)
排序算法算是最为简单经典的算法问题了,因此从这个开始学习记录,以加深印象。
其中常见的排序算法有:
选择排序冒泡排序插入排序合并排序快速排序堆排序
以上排序算法一定无法罗列全部排序算法的大家族,但是暂且讨论以上的算法。
选择排序和冒泡排序属于蛮力解决问题的表现; 插入排序则使用减治法; 合并排序和快速排序使用分治法; 堆排序使用变治法。
选择排序
蛮力法去解决排序问题没有那么多弯弯道,选择排序的思路:
n个元素,先找到最小的元素,然后将它交换到它该在的位置,对于升序来说即第一个位置,然后第一个元素就是有序元素了,随后再将从剩下的n-1个寻找最小的元素,放到第二个位置上,以此类推,交换n-1次就可以得到一个有序的集合了。
实现代码
int ChooseSort(arr* a) {//使用选择排序//输入:无序元素列表//输出:成功返回1,失败返回0for (int i = 0; i < a->length - 1; i++) {int min = i;for (int j = i; j < a->length; j++) {if (a->ite[min] > a->ite[j]) {min = j;}}if (!Swap(a, i, min)) {return 0;}}return 1;}
冒泡排序
冒泡排序很形象,过程也和冒泡一样,思路:
从第一个元素开始,比较相邻元素,若是有序,则不变,若是无序,则交换相邻元素,这样做的结果就是会将最大的元素给“顶”到最后一个位置,接着将上述过程在前n-1个元素中重复。以此类推,最后就会得到一个有序的集合。
代码实现:
int BubbleSort(arr * a){//使用冒泡排序得到有序列表//输入:无序元素的列表//输出:成功返回1,失败返回0for (int i = a->length; i > 0; i--) {for (int j = 0; j < i-1; j++) {if (a->ite[j] > a->ite[j + 1]) {if (!Swap(a, j, j + 1)) return 0;}}}return 1;}
插入排序
记得第一次看到插入排序,书上是拿扑克牌举例的,思路:
我们先认为列表的第一个元素是有序的,那么拿起第二个元素,寻找在前面第一个元素的合适的位置,插进去,现在有序的集合元素就变成两个了。以此类推,第三个找到合适的位置插入,一直到第n个元素,这样,就得到了有序元素的集合。
代码实现:
int InserSort(arr * a){//使用插入排序//输入:无序元素的列表//输出:返回1for (int i = 1; i < a->length; i++) {for (int j = 0; j < i; j++) {if (a->ite[j] >= a->ite[i]) {int temp = a->ite[i];for (int k = i - 1; k >= j; k--)a->ite[k + 1] = a->ite[k];a->ite[j] = temp;}}}return 1;}
合并排序
合并排序是使用递归的思路来做的,也即上文提到的分治法。思路:
将其中每一个元素都看作为有序的集合,虽然每个集合只有一个元素,然后将两个有序集合合并成一个,依次合并,最终就生成了最后的有序集合。
代码实现:
int MergeSort(arr * a){//使用合并排序//输入:无序元素列表//输出:成功返回1if (a->length > 1) {arr *a1 = Cut(a, 0, a->length / 2 - 1);arr *a2 = Cut(a, (a->length / 2), a->length - 1);MergeSort(a1);MergeSort(a2);arr* b = Merge(a1, a2);for (int i = 0; i < b->length; i++) {a->ite[i] = b->ite[i];}a->length = b->length;free(a1); free(a2); free(b);}return 1;}
这是上述代码中Merge函数,即合并有序集合的函数:
arr * Merge(arr * a1, arr * a2){//合并过程,将两个有序列表合并成一个有序列表,并释放这两个有序列表内存//输入:两个有序列表//输出:一个有序列表arr *a = (arr*)malloc(sizeof(arr));a->length = 0;int i, j, k;for (i = 0, j = 0, k = 0; i < a1->length && j < a2->length; k++) {if (a1->ite[i] > a2->ite[j]) {a->ite[k] = a2->ite[j];j++;}else{a->ite[k] = a1->ite[i];i++;}a->length++;}if (i == a1->length) {for (; j < a2->length; j++, k++) {a->ite[k] = a2->ite[j];a->length++;}}else{for (; i < a1->length; i++, k++) {a->ite[k] = a1->ite[i];a->length++;}}return a;}
快速排序
快速排序与前面的合并排序一样,也用到了递归的思想。但是在实际实现上与合并排序有很大的不同,合并排序在实现上倾向于合并上,即将每个有序元素集合合并成一个更大的有序元素集合。快速排序则是划分与交换,从线性集合的两端开始,选取基准数,用基准数将整个集合划分为两个区间,左边全部是比基准数小的数,右边全部是比基准数大的数。然后通过分治法继续划分下去,而划分则是通过交换来实现。
代码实现:
int QuickSort(arr * a, int l, int m){//实现快速排序算法//输入:无序元素列表a,列表开始区间坐标和结束区间坐标//输出:成功返回1int s;if (l < m) {s = PartPostion(a, l, m);QuickSort(a, l, s-1);QuickSort(a, s+1, m);}return 1;}
其中的ParPosition函数如下:
int PartPostion(arr* a, int l, int m) {//实现快速排序算法中的划分区间//输入:无序元素列表a,列表开始区间坐标和结束区间坐标//输出:作为中轴的下标int i = l, j = m;int key = a->ite[l];while (i < j) {while (key > a->ite[i] && i < m) {i++;}while (key < a->ite[j]) {j--;}Swap(a, i, j);}Swap(a, i, j);Swap(a, i, j);return j;}
堆排序
堆排序顾名思义,用到了堆,最大堆就是一棵完全二叉树,其中的每一个节点的值都要大于其子女的值。
堆排序的具体思路正是用到了这个最大堆:
使用这些数构造一个最大堆,然后删除堆的最大键。以此类推,便可得到有序元素的集合。其中删除最大键的操作其实就是删除最大堆的根,先将根与堆最后的元素进行交换,然后删除最后的元素,即交换后的根,然后把此时在根上的那个小数再拉下来,让大数顶上去即可。
代码实现:
int HeapSort(arr * a){//使用堆排序的算法排序//输入:无序元素列表//输出:成功返回1int size = a->length;BuildHeap(a, size);while (size != 1) {Swap(a, 0, size - 1); size--;BuildHeap(a, size);}return 1;}
以上实现的BuildHeap函数如下,作用为构造最大堆:
int BuildHeap(arr* a, int size) {//构造一个最大堆//输入:要转化成最大堆的无序元素列表和要生成最大堆的规模//输出:成功返回1for (int n = size/2; n > 0; n--)for (int i = size - 1; i > 0; i--)if (a->ite[(i - 1) / 2] < a->ite[i]) Swap(a, (i - 1) / 2, i);return 1;}
这里我使用了从底而上的构建堆的方法。
总结
这些排序前三个思路都比较简单,尤其是前两个蛮力法的选择排序与冒泡排序。那两个分治法的排序方法还是不太行,合并排序感觉上要比快速排序好懂点,快速排序在通过交换来划分区间的方法感觉还是不太理解,剩下的堆排序感觉上也比较简单。
标签:
相关推荐:
最新新闻:
- 求正弦函数的值怎么算?python求正弦函数的值
- 全球最资讯丨神州行幸福卡是什么?神州行幸福卡详情介绍
- 即时看!第一章begining c语言中的变量与对象
- 工业机器人技术全解析 工业机器人的发展背景及应用场景
- 每日播报!怎么登入192.168.0.1路由器的管理页面?详细步骤
- hplaserjetp1008打印机驱动安装失败怎么办?解决方法步骤
- 无线路由器怎么设置?TP-LINK无线路由器设置教程_当前观点
- 华为鸿蒙系统怎么安装第三方软件?安装方法步骤
- 用Python3实现dota改建精灵——python库
- VR技术:打破传统呈现创新性的虚拟三维动画|当前滚动
- mac卡巴斯基激活码怎么用?免费领取教程来了
- 全球报道:万利达电磁炉怎么样?万利达电磁炉相关介绍
- 热点评!各种常见排序算法实现 常见排序算法汇总
- 三星i458怎么样?报价多少?三星i458市场报价及测评
- 软件更新方法有哪些?软件更新方法远程更新:世界短讯
- 天天速讯:两台未联网的Win7电脑怎么建立局域网游戏?操作步骤
- 简讯:湿帘冷风机原理是什么?湿帘冷风机的作用与工作原理
- 维纳滤波是最优的线性滤波器 矩阵&向量的求导方法
- 科龙空调遥控器怎么用?科龙空调遥控器使用方法
- 山煤国际(600546)2月9日主力资金净买入4135.05万元
- 控制寄存器和命令寄存器的英文理解(一)_世界今头条
- hive中Buckets详解 Buckets指定列计算hash
- 天天视点!豆芽是怎么生长的?豆芽的生长过程观察日记
- 年货从不缺席!今年还是会有《使命召唤》游戏|当前热议
- 滚动:无双工作室带来《狂野之心》15分钟试玩演示
- 极限超频 撼讯科技Powercolor7900XTX水冷!|环球实时
- 林克坐上无人机?《塞尔达王国之泪》新预告片发布
- 美股市场反弹,华尔街几近冰冻的IPO开始回暖
- 产品太贵无法拿政府补贴,美电动车商Lucid自掏腰包加入优惠战
- 现货4090游戏本 机械革命旷世X新品24999元:全球热议
- 环球新资讯:梦回童年 任天堂上线GB和GBA游戏
- 快消息!100美元部件导致维珍轨道发射失败
- 恋爱动作《永恒之夜》推迟至初夏发行 新预告展示:播资讯
- “非洲之王”传音首款折叠屏手机官宣 天玑旗舰芯
- 《霍格沃茨之遗》PS5限定手柄公布!明日发售 世界时快讯
- 世界最新:刘亚仁涉毒,顶流影帝一夜面临崩塌
- 任天堂公布《超级马里奥兄弟电影》碧琪公主专属海报-每日焦点
- 《原子之心》详细PC配置公布 推荐2070S、硬盘90G
- 三星最好的平板电脑_三星平板电脑推荐_三星平板推荐 环球报资讯
- Netflix的密码共享打击措施在加拿大、新西兰、葡萄牙和西班牙开始实施 热门看点
- 环球关注:性能炸裂!英特尔酷睿i9-13980HX登顶笔记本跑分榜
- 全国养老保险个人账户查询官网_个人养老保险查询个人账户查询官网 每日资讯
- 环球热门:模特王鲲鹏,王鲲鹏电影,王鲲鹏个人资料
- 微动态丨广州大道北华快节点跨线桥正式开放
- Fami通新一周销量榜 《精灵宝可梦朱/紫》再登顶_天天热讯
- 被14岁粉丝表白 周星驰:年轻人不应过度沉迷我美色:全球热讯
- 世界最新:网课留学,即将成为历史
- 「围攻」特斯拉:每日简讯
- 男士毛衣品牌推荐_男士毛衣品牌
- 安卓14发布首个版本:可双开APP了_世界最新
- 真我GT Neo5发布:240W快充 2499元起
- 华硕发布新路由器:首次加入双2.5G网口
- 新动态:38999元 雷蛇发新笔记本:24核i9+RTX 4090
- 大精神在基层(五十八)丨瀍河分局:民警真情救助群众暖人心
- 环球快看:外媒发起任天堂直面会观众投票:《塞尔达传说:王国之泪》不敌《银河战士Prime复刻版》屈居第三
- 漂移竞速游戏《Drift CE》公布 今春登陆主机
- 迪士尼裁员7000人 可降低55亿美元成本
- 我,黄山谷,出门一笑大江横,这人间来过了 世界资讯
- 如今爆火的AIGC,会成为下一个泡沫破灭的NFT嘛?
- 国外玩家猜测PS5新机型是否涨价:标准版价格与数字版一致 光驱单卖100美元-环球快资讯
- 玩家猜测:《塞尔达传说:王国之泪》新载具系统是受各种玩家在《旷野之息》骚操作的启发
- 【聚看点】“零成本”月入数10万,盗版ChatGPT成提款机
- Lattice Avant:拓展FPGA市场的广阔空间
- 环球报道:苹果或推Apple Watch X系列,屏幕再变大
- 航世有线红轴键盘跌至77元:搭载国产红轴 87键设计
- 【环球时快讯】续航虚标乱象或终结,爱玛联合中标院推出测试新标准,龙头业绩有望持续兑现
- 任天堂直面会前推特出现特大技术问题 引发玩家众怒
- 小摩减持新秀丽约43.71万股 每股作价约23.19港元 快消息
- 散户也能吊打机构?:全球速看
- 尼康发布财报:影像业务亮点不断 营业利润同比增长超200%
- 大疆Mini 2 SE今天发布:不到249克续航31分钟 预售2388元
- iPhone出货量同比跌14%!但营收创新高
- 直降1100元!酷睿i5-12490F+RTX3050游戏主机史低价4499元
- 【环球播资讯】办公、游戏首选:联合创新27英寸4K显示器低至1399元
- 长江七号片尾曲叫什么名字-天天时讯
- 热讯:SE公开克劳德女装晚礼服手办 双马尾少女感十足
- 外网论坛2022最佳游戏原声投票:《异度之刃3》夺冠 全球速读
- 东京国际动画节公布年度动画大奖 海贼王间谍过家家获奖:环球播资讯
- 趋势难挡!美法公司推4天工作制:不减薪 提升幸福度
- 伯克希尔哈撒韦公司于2月3日出售了424万股比亚迪H股股票,持股比例降至11.87%。
- Nature封面论文惨遭撤稿,人类的室温超导梦碎了?|全球快讯
- 苹果Apple Watch Ultra立减1130元,价格新低
- 开学季 用长虹激光电视安抚孩子们的开学小情绪_新要闻
- 【环球新要闻】配4800万像素主摄?iPhone 15/15 Plus将获得“新的相机凸起”
- Pixel 7 Pro有超过50%的组件来自三星-天天滚动