引入📕
今天,我们来学习一种排序算法——冒泡排序。
首先,先问三个问题:
1.为什么要排序?🔥
想象一下,如果字典不是按照字母顺序排列,查找一个单词,你得查到什么时候?这就是为什么人们引入了分类的概念,因为其极大地帮助我们快速搜索物品。
或者说,排序是一种常用的整理信息的方法。排序可克服资料混乱、不便交流、查阅困难、挑选或取舍困难、不便安排等等问题。
2.有那些常用的排序算法?⌚
冒泡排序、选择排序、插入排序、归并排序等等都是常用的排序算法。
各种排序的复杂度、方式等方面都略有不同,下面这张图可以反映(图片参考自常用十大排序算法):
3.什么是冒泡排序?🔨
冒泡排序(Bubble Sort),是一种 计算机科学领域的较简单的 排序算法。
它重复地走访过要排序的元素列,依次比较两个相邻的 元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行,直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中 二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
这是百度的说法,让我们来看看另一种说法。
冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小,再根据结果交换两个数字的位置”这一操作的算法。在这个过程中,数字会像泡泡一样,慢慢从右往左“浮”到序列的顶端,所以这个算法才被称为“冒泡排序”。
来自《我的第一本算法书》。
总的来说,就是一句话:
通过不断比较相邻元素,将大的元素放到数组后面,最终完成排序。
这具体是什么原理呢?请看下面。
原理❓
文字解释📌
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
举个栗子(文字说明)👔
对6 3 2 5 4 1 这个乱序数字串进行冒泡排序。
第一步.3 2 5 4 1 6
第二步.2 3 4 1 5 6
第三步.2 3 1 4 5 6
第四步.2 1 3 4 5 6
第五步.1 2 3 4 5 6
这样就完成了。
举个栗子(图文混合说明)🌏
注:此处与上面的排序不太一样,上面是把大的优先放在后面,这是把小的依次放到前面。
在序列的最右边放置一个天平,比较天平两边的数字。如果右边的数字较小,就交换这两个数字的位置。
由于6<7,所以交换这两个数字。
完成后,天平往左移动一个位置,比较两个数 字的大小。此处4<6,所以无须交换。
继续将天平往左移动一个位置并比较数字。重复同样的操作直到天平到达序列最左边为止。
不断对数字进行交换,天平最终到达了最左边。通过这一系列操作,序列中最小的数字就会移动到最左边。
最左边的数字已经归位
将天平移回最右边,然后重复之前的操作,直到天平到达左边第2个位置为止
当天平到达左边第2个位置时,序列中第2小的数字也就到达了指定位置。
将天平再次移回最右边,重复同样的操作直到所有数字都归位为止
排序中…
排序完成。
一些说明😱
时间复杂度
在冒泡排序中,第 1 轮需要比较 n -1 次,第 2 轮需要比较 n -2 次……第 n -1 轮需 要比较 1 次。因此,总的比较次数为 (n -1) +(n -2) +…+1 ≈ (n^2)/2。这个比较次数恒定为该数值,和输入数据的排列顺序无关。
不过,交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况,如输 入数据正好以从小到大的顺序排列,那么便不需要任何交换操作;反过来,输入数据要 是以从大到小的顺序排列,那么每次比较数字后便都要进行交换。因此,冒泡排序的时间复杂度为 O(n^2 )。
两种不同的比较方法
相信大家都注意到了,文字说明与图文混合说明比较顺序是不同的。一个是把最大,第二大,第三大,...第n大依次放到后面;一个是把最小,第二小,...,第n小依次冒到前面。
不过,它们都是冒泡排序!
程序实现💐
注:此处用的是把最大,第二大,第三大,...第n大依次放到后面的冒泡顺序。
步骤图
代码😇
不用说了,很简单。(只插入中心部分)
for(int i=n;i>=1;i--)
{
for(int j=1;j<i;j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
}
}
}
优化👆
问题
数据的顺序排好之后,冒泡算法仍然会继续进行下一轮的比较。很显然,后面的比较没有意义的。
解决办法📐
设置bool变量flag(用于标记),如果发生了交换flag设置为true;如果没有交换就设置为false。
这样当一轮比较结束后如果flag仍为false,即:这一轮没有发生交换,说明数据的顺序已经排好,没有必要继续进行下去。那么,就可以结束排序了。文章来源:https://www.toymoban.com/news/detail-602463.html
最终代码🔭
bool b;
for(int i=n;i>=1;i--)
{
b=false;
for(int j=1;j<i;j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
b=true;
}
}
if(b==false) break;
}
结语
冒泡很简单,但是排序算法的基础。必须学会!文章来源地址https://www.toymoban.com/news/detail-602463.html
到了这里,关于c++排序算法——冒泡排序(不会的一定要看,超级详细)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!