c++ 排序算法 - 冒泡排序（不懂必读，超级详细）

引入????

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

首先，先问三个问题：

1.为什么要排序？????

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

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

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

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

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

3.什么是冒泡排序？????

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

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

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

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

总的来说，就是一句话：

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

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

原理❓

文字解释????

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

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

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

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

举个栗子（文字说明）????

对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]);
            }
        }
    }

上一篇： 气泡排序的经典算法（简略版）

下一篇： 一分钟内透彻理解 JavaScript 的气泡排序和选择排序功能