假设对数组arr=[9,1,5,8,3,7,4,6,2]由小到大排序
方式一:
从左到右遍历,把每个位置确定下来。
for(i=0;i<len-1;i++){
for(j=i+1;j<len-1;j++){
if(arr[j]>arr[i]){
swap
执行顺序:
1,9,5,8,3,7,4,6,2//只换一次,就确定第1个位置的数据
1,5,9,8,3,7,4,6,2
1,3,9,8,5,7,4,6,2
1,2,9,8,5,7,4,6,3//交换了三次,但是把3居然交换到最后了,这会导致下一次的循环交换次数增加。所以出现更优化的方式二
……
方式二:
仍然是从左到右遍历,确定每个位置的数值。但是内部的循环方式不一样。
for(i=0;i<len-1;i++){
for(j=len-1;j>=i;j--){//从尾部开始循环
if(arr[j]>arr[j+1]){//把小的往前排,就像冒泡一样
swap
9,1,5,8,3,7,4,2,6
9,1,5,8,3,7,2,4,6
9,1,5,8,3,2,7,4,6
9,1,5,8,2,3,7,4,6
9,1,5,2,8,3,7,4,6
9,1,2,5,8,3,7,4,6
1,9,2,5,8,3,7,4,6
继续第二遍循环
1,9,2,5,8,3,4,7,6
1,9,2,5,3,8,4,7,6
1,9,2,3,5,8,4,7,6
1,2,9,3,5,8,4,7,6
……
可以看出,优化主要集中在减少swap次数。方式一会把一个很小的数扔到最后,导致后续的无效swap次数增多。方式二在循环的过程中,一直把小的数字往前调整,直到调整不动为止。可以看出,swap都是有效的。即使前期swap增多,后期swap也会大大减少。
方式二的进一步优化:
假如数组排序前就是2,1,3,4,5,6,7,8,9呢,这样第一次交换后,就已经排好序,后面的比较都浪费了。怎么才能让程序知道已经排好序了呢,答案就是冒泡时发现一个泡都冒不动了。
boolean flag = true;
for(i=0;(i<len-1)&&flag;i++){//
flag = false;
for(j=len-1;j>=i;j--){//从尾部开始循环
if(arr[j]>arr[j+1]){//把小的往前排,就像冒泡一样
flag = true;
swap
可以看出,假如没有swap,flag就会变成false导致循环立即退出。
相关推荐
LabVIEW实现冒泡算法求数组最大值
C语言冒泡排序算法源程序,冒泡排序算法的思路即两两进行大小比较,交换排序,通过相邻数据的比较交换从而实现排序目的。
JAVA 演示冒泡算法 内有动画演示 问题 有一数组a,长度为n,把数组中的元素从小到大重新排列 思路 从0到n-1,两两比较数组中的元素,如果前者大于后者,则交换之(如a[0]>a[1],则交换a[0]和a[1])。作一...
C语言冒泡排序及流程图思路解析
本文件包含冒泡排序的基本思路,代码实现,时间复杂度的分析。对数据结构与算法中冒泡排序算法的实现,附件以python语言实现。
常见的四种排序算法是:简单选择排序、冒泡排序、插入排序和快速排序。其中的快速排序的优势明显,一般使用递归方式实现,但遇到数据量大的情况则无法适用。实际工程中一般使用“非递归”方式实现。本文搜集发布四种...
常用排序算法总结,包括插入排序(InsertionSort),冒泡排序(BubbleSort),选择排序(SelectionSort),快速排序(QuickSort), * 二路归并排序(MergeSort),堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现...
在众多排序算法中,冒泡排序是最基础和最简单的一种。 冒泡排序的基本思想是通过不断比较相邻元素并交换它们的位置,使得较大的元素逐渐“浮”到数组的末端。这个过程会不断重复,直到整个数组都有序为止。虽然冒泡...
冒泡算法是一种基础的排序算法,这种算法会重复的比较数组中相邻的两个元素。如果一个元素比另一个元素大(小),那么就交换这两个元素的位置。重复这一比较直至最后一个元素。这一比较会重复n-1趟,每一趟比较n-j次...
有关数据结构中冒泡排序的简便算法。
针对初学数据结构的学生学习了解。虽然冒泡排序的效率不高。但是是排序里面的一个基本思路,可以了解。面试的时候,一般面试官也可能问道
1.排序算法:常见的排序算法包括冒泡排序、选择排序、插入排序、 归并排序等,需要熟练掌握其原理、时间复杂度及实现方法。 2.搜索算法:包括深度优先搜索(DFS)和广度优先搜索(BFS),在 图论、树的遍历等场景下...
常见的四种排序算法是:简单选择排序、冒泡排序、插入排序和快速排序。其中的快速排序的优势明显,...算法思路:从左到右,以第一个元素作为基准数与后面的数作比较,找到比它小的数就交换。以此类推。直至循环结束。
一般图问题与二分图问题的转换思路 最大匹配(OK) 有向图的最小路径覆盖 0 / 1矩阵的最小覆盖 完备匹配(OK) 最优匹配(OK) 稳定婚姻 网络流问题 网络流模型的简单特征和与线性规划的关系 最大流最小...
一套入门算法总结,适合新手,常用算法,比如 冒泡,快速,归并等,用了好几种语言编写,重在解法思路,而不是语言本省,适合新手。
主要包括冒泡排序(两种思路实现)、冒泡排序的改进算法、选择排序法、插入排序法(两种实现方式)、快速排序法、归并排序法 (递归实现和非递归实现),该资料为本人亲自整理,且代码完整、注释全面!
思路:对数组进行多轮冒泡,每一轮对数组中的元素两两比较,调整位置,冒出一个最大的数来。 //简单版: function bubbleSort($arr) { $n = count($arr); for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮) ...
使用冒泡算法对其进行排序 找到链表中倒数第k个节点 不同实现 设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点 (-k+1+链表总数) % 链表总数 ...
⑴ 编程实现内部排序算法:编程实现直接插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,堆排序,归并排序算法。 ⑵ 要求数据规模:待排序数据类型不限(整型或浮点型),读取自磁盘文件。需用多组、多规模...
这里提供了冒泡排序,插入排序,递归排序,基数排序,快速排序,选择排序,希尔排序这几种排序算法。里面有大量的注释,可以理解实现思路