| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> 算法(排序算法之冒泡排序及其变式) -> 正文阅读 |
|
[数据结构与算法]算法(排序算法之冒泡排序及其变式) |
(此篇实现语言为C语言) 冒泡排序可能是我们在学习谭浩强C语言里面比较痛苦的算法之一了,不少人也因为缺少对于双重循环的把控而出现写不出以及处处出错的问题。今天也是来谈谈作为交换排序之一的冒泡排序究竟是如何实现的。
在这里为大家准备一个待排序的数组: ?而我们的冒泡排序是如何将这个无序的数组转化为有序的呢? 首先要明白,冒泡排序是两个数之间进行比较,将较大的数字放置在小的数字之后(由小到大排序,由大到小反之,本文全篇探讨由小到大排序),而每次我们的比较完了以后步长为1地往下继续比较,这样便会出现有趣的现象: ?(画的可能有点抽象,大家请自行脑补一下。。。)我们每次进行两两比较,大的元素后置,也就是大的泡泡往上不断往上水面上浮,每次都会将最大的元素后置,也就是最大的泡泡到了最接近水面的地方,而到第一次的排序的最后,我们也会发现,最大的元素被放置到了最后。 ?虽然前面仍然是无序的,但我们至少把最大的元素放到了最后不是?于是我们每次将数组遍历的长度减一,把最大的元素放到最后,那么最后不就是一个有序的数组吗?相当于每次最大的泡泡都会冒出水面,第二次的时候,第二大的泡泡直接作为最大的泡泡往上冒出水面,以此类推,直至所有的泡泡冒出水面。 大伙也可以自己尝试脑子里跑一边第二轮的冒泡排序 ?九轮之后,我们将九个元素全部置成我们脑海中逻辑数组(也就是每次减少一个遍历长度的所抽象出来的数组)的最大位上,即得到了一个有序数组{ 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9? } 那我们的代码应该如何实现呢,每次比较最大的元素都需要后置,且每次比较完成,数组的遍历长度就需要减一.
通过内外两层循环,外层控制总的冒泡次数,内层控制执行一次的冒泡排序,整个冒泡排序也就在我们的掌握之中咯。 但是,如果我们给出的数组是本身是有序的呢? 是不是那么多次的冒泡其实是没有必要的,小的泡泡完全没必要跟脑袋上的泡泡比较看看是不是要往上浮,我们只需要在第一轮的全遍历中知道这是一个有序数组然后直接出循环即可。 这里,就需要一个flag标志变量了,我们的pro版本也仅需要一个flag就升级成功。
我们的单向冒泡程序完成,但是我们同时需要想到一个问题,我们每一次的冒泡过程是不是已结束我们的索引就需要回到最初的位置重新进行下一遍的冒泡,这就没有实现时间的统筹安排嘛,你想想,我们走一遍过去是一个冒泡,走回来还是一个冒泡,这不就是来回都有事干,这才不浪费时间,我们的计算机打工人也能被完美的调用起来。? 在这里也是对我们循环掌握度提高了更高层次的要求。 接下来是图解流程: 向右迈步,将最大元素右置 ,而接下来: 那我们下一轮呢?自己不妨想一下: ?就这样我们执行双向冒泡 length/2取整?次(length为数组长度)之后我们便能得到有序的数组。 接下来我们来程序实现:
无独有偶,我们应该也要向之前单向冒泡一样考虑最好的状况,即有序数列,仅需一个标志变量即可,十分的简单,既然在之前已经知道了单向冒泡要去如何添加标志变量,双向冒泡可以自己尝试一下添加标志变量。
?(如有问题,欢迎指正) |
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 | -2025/1/9 15:45:23- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |