【经典算法】冒泡排序
冒泡算法
冒泡排序:从序列的一端开始往另一端冒泡,依次比较相邻的两个数的大小。
设数组长度为N。
1.每轮比较相邻的前后两个数据,如果前面数据大于或者小于后面的数据,就将二个数据交换。
2.这样每轮对数组的第0个数据到N-1个数据进行一次遍历后,最大或者最小的一个数据就到数组第N-1个位置。
3. 第一轮比较到下标为N-1的数据(最后一个),以后每次比较都-1。
#include <stdio.h> int main () { int list[10] = {5,23,86,21,43,67,45,34,58,23}; int i, j, temp; for (i = 0; i < 10 - 1 ; i++) for (j = 1; j < 10 - i; j++) if (list[j - 1] > list[j]) { temp = list[j - 1]; list[j - 1] = list[j]; list[j] = temp; } for (i = 0;i < 10; i++) printf("%d\n",list[i]); }
优化算法
冒泡有一个最大的问题就是不管序列有序还是没序,双层循环的每一次比较都执行了。
下面对其进行优化,设置一个标志,如果这一轮发生了交换,则为1,否则为0。
如果有一趟没有发生交换,说明排序已经完成,则结束排序。
#include <stdio.h> int main () { int list[10] = {5,23,86,21,43,67,45,34,58,23}; int j, temp; int i = 10; int bool = 1; while(bool) { bool = 0; for (j = 1; j < i; j++) if (list[j - 1] > list[j]) { temp = list[j - 1]; list[j - 1] = list[j]; list[j] = temp; bool = 1; } i--; } for (i = 0;i < 10; i++) printf("%d\n",list[i]); }
图解冒泡排序
以 [ 8,2,5,9,7 ] 这组数字来做示例:
从左往右依次冒泡,将小的往右移动
第一轮冒泡:
首先比较第一个数和第二个数的大小,我们发现 2 比 8 要小,那么保持原位,不做改动。位置还是 8,2,5,9,7 。
指针往右移动一格,接着比较:
比较第二个数和第三个数的大小,发现 2 比 5 要小,所以位置交换,交换后数组更新为:[ 8,5,2,9,7 ]。
指针再往右移动一格,继续比较:
比较第三个数和第四个数的大小,发现 2 比 9 要小,所以位置交换,交换后数组更新为:[ 8,5,9,2,7 ]
同样,指针再往右移动,继续比较:
比较第 4 个数和第 5 个数的大小,发现 2 比 7 要小,所以位置交换,交换后数组更新为:[ 8,5,9,7,2 ]
下一步,指针再往右移动,发现已经到底了,则本轮冒泡结束,处于最右边的 2 就是已经排好序的数字。
通过这一轮不断的对比交换,数组中最小的数字移动到了最右边。
第二轮冒泡:
由于右边的 2 已经是排好序的数字,就不再参与比较,所以本轮冒泡结束,本轮冒泡最终冒到顶部的数字 5 也归于有序序列中,现在数组已经变化成了[ 8,9,7,5,2 ]。
第三轮冒泡:
由于 8 比 7 大,所以位置不变,此时第三轮冒泡也已经结束,第三轮冒泡的最后结果是[ 9,8,7,5,2 ]
第四轮冒泡:
9 和 8 比,位置不变,即确定了 8 进入有序序列,那么最后只剩下一个数字 9 ,放在末尾,自此排序结束。
相关文章
- 机器学习十大经典算法之朴素贝叶斯分类
- 机器学习十大经典算法之最小二乘法
- 经典算法–约瑟夫环问题的三种解法
- 圣杯布局、双飞翼布局、Flex布局和绝对定位布局的几种经典布局的具体实现示例
- 贪心算法及几个经典例子c语言_贪心算法一定是最优解吗
- 一次生产环境P0级事故分析(经典)
- Java算法大全_java贪心算法几个经典例子
- 动画图解:十大经典排序算法动画与解析,看我就够了!(配代码完全版)[通俗易懂]
- 《异常检测——从经典算法到深度学习》6 基于重构概率的 VAE 异常检测
- 【Java面向对象】学习Java经典必刷题库
- 实例分析运放7大经典电路
- 【最全总结】离线强化学习(Offline RL)数据集、Benchmarks、经典算法、软件、竞赛、落地应用、核心算法解读汇总
- 关于递归算法的优化Ⅰ(以经典的斐波那契数列为例)
- 企业综合运维监控项目经典案例
- 《机器学习十大经典算法》报告邀请
- 回溯算法的经典应用 - 排列与组合
- 独家 | 三个经典强化学习算法中重大缺陷(及如何修复)
- 经典排序算法:堆排序(Heap Sort)详解编程语言
- 经典排序算法:冒泡排序(Bubble Sort)详解编程语言
- Java经典问题算法大全详解编程语言
- Linux系统运维面试:探究经典之路(linux系统运维面试题)
- C/C++经典网站详解编程语言
- MySQL经典1607版本更新(mysql1607)
- haproxy经典入门教程
- 每个程序员应该阅读的10本经典书籍
- MySQL经典试题:备战面试(mysql经典试题)
- Oracle实战经典:让你成功实现跨越式发展。(oracle 实战经典)
- 分享Redis面试中的经典问题(redis面试经典问题)
- php代码优化之经典示例
- asp经典入门教程在ASP中使用SQL语句