c++排序算法——冒泡排序(不会的一定要看,超级详细)

这篇具有很好参考价值的文章主要介绍了c++排序算法——冒泡排序(不会的一定要看,超级详细)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

引入📕

今天,我们来学习一种排序算法——冒泡排序

首先,先问三个问题:

1.为什么要排序?🔥

想象一下,如果字典不是按照字母顺序排列,查找一个单词,你得查到什么时候?这就是为什么人们引入了分类的概念,因为其极大地帮助我们快速搜索物品

或者说,排序是一种常用的整理信息的方法。排序可克服资料混乱、不便交流、查阅困难、挑选或取舍困难、不便安排等等问题

2.有那些常用的排序算法?⌚

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

冒泡排序、选择排序、插入排序、归并排序等等都是常用的排序算法。

各种排序的复杂度、方式等方面都略有不同,下面这张图可以反映(图片参考自常用十大排序算法):

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

3.什么是冒泡排序?🔨

冒泡排序(Bubble Sort),是一种 计算机科学领域的较简单的 排序算法。
它重复地走访过要排序的元素列,依次比较两个相邻的 元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行,直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中 二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

这是百度的说法,让我们来看看另一种说法。

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小,再根据结果交换两个数字的位置”这一操作的算法。在这个过程中,数字会像泡泡一样,慢慢从右往左“浮”到序列的顶端,所以这个算法才被称为“冒泡排序”。

来自《我的第一本算法书》。

总的来说,就是一句话:

通过不断比较相邻元素,将大的元素放到数组后面,最终完成排序。

这具体是什么原理呢?请看下面。


原理❓

文字解释📌

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  1. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

  1. 针对所有的元素重复以上的步骤,除了最后一个。

  1. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

举个栗子(文字说明)👔

对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

这样就完成了。

举个栗子(图文混合说明)🌏

注:此处与上面的排序不太一样,上面是把大的优先放在后面这是把小的依次放到前面。

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

在序列的最右边放置一个天平,比较天平两边的数字。如果右边的数字较小,就交换这两个数字的位置。

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

由于6<7,所以交换这两个数字。

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

完成后,天平往左移动一个位置,比较两个数 字的大小。此处4<6,所以无须交换。

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

继续将天平往左移动一个位置并比较数字。重复同样的操作直到天平到达序列最左边为止。

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

不断对数字进行交换,天平最终到达了最左边。通过这一系列操作,序列中最小的数字就会移动到最左边。

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

最左边的数字已经归位

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

将天平移回最右边,然后重复之前的操作,直到天平到达左边第2个位置为止

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

当天平到达左边第2个位置时,序列中第2小的数字也就到达了指定位置。

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

将天平再次移回最右边,重复同样的操作直到所有数字都归位为止

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

排序中…

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

排序完成。


一些说明😱

时间复杂度

在冒泡排序中,第 1 轮需要比较 n -1 次,第 2 轮需要比较 n -2 次……第 n -1 轮需 要比较 1 次。因此,总的比较次数为 (n -1) +(n -2) +…+1 ≈ (n^2)/2。这个比较次数恒定为该数值,和输入数据的排列顺序无关。

不过,交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况,如输 入数据正好以从小到大的顺序排列,那么便不需要任何交换操作;反过来,输入数据要 是以从大到小的顺序排列,那么每次比较数字后便都要进行交换。因此,冒泡排序的时间复杂度为 O(n^2 )

两种不同的比较方法

相信大家都注意到了,文字说明与图文混合说明比较顺序是不同的。一个是把最大,第二大,第三大,...第n大依次放到后面;一个是把最小,第二小,...,第n小依次冒到前面。

不过,它们都是冒泡排序


程序实现💐

注:此处用的是把最大,第二大,第三大,...第n大依次放到后面的冒泡顺序。

步骤图

c++冒泡排序,算法大图详解,排序算法,c++,算法,Powered by 金山文档

代码😇

不用说了,很简单。(只插入中心部分)

    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,即:这一轮没有发生交换,说明数据的顺序已经排好,没有必要继续进行下去。那么,就可以结束排序了。


最终代码🔭

    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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包