C++中常用的十大排序方法之1——冒泡排序

 成长路上不孤单😊😊😊😊😊😊

【😊///计算机爱好者😊///持续分享所学😊///如有需要欢迎收藏转发///😊】

今日分享关于C++中常用的排序方法之——冒泡排序的相关内容！

关于【C++中常用的排序方法之——冒泡排序】

目录：

• 一、 冒泡排序的定义
• 二、冒泡排序的算法原理
• 三、冒泡排序的算法示例
• 四、冒泡排序的算法分析
• 五、冒泡排序的特点
• 六、冒泡排序的优点
• 七、冒泡排序的缺点

冒泡排序（Bubble Sort）‌

一、冒泡排序的定义

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。
大家一定都喝过汽水，汽水中常常有许多小小的气泡，哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻，所以小气泡可以一点一点向上浮动。而我们的冒泡排序之所以叫做冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。

  

二、冒泡排序的算法原理

假定序列中有n个数，要进行从小到大的排序。若参与排序的数组元素共有n个，则需要n-1轮排序。在第í轮排序中，从左端开始，相邻两数比较大小，若反序则将两者交换位置，直到比较第n+1-i个数为止。第1个数与第2个数比较，第2个数和第3个数比较，一直到第n-i个数与第n+1-i个数比较，一共处理 n-i次。此时，第n+1-i个位置上的数已经有序，后续就不需要参加以后的排序。 

（1）第1轮冒泡排序先从第1个数和第2个数开始比较，若第1个数大于第2个数，则需要交换两者的位置；否则保持不变。重复这一过程，直到处理完本轮数列中最后两个数。 

（2）第2轮冒泡排序与第1轮冒泡排序进行相同的排序，使大的数交换到n-2的位置上。 

（3）重复以上过程，共需经过n-1轮冒泡排序后，数据实现升序排序。

三、冒泡排序的算法示例

对于序列[26，28，24，11]，采用非递减规则进行排序，排序过程如下所示。 

  

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

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

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

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

四、冒泡排序的算法分析

1、时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数

  

    

若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i 次，关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

  

  

2、算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

五、冒泡排序的特点

‌ 时间复杂度‌：冒泡排序的时间复杂度为O(n^2)。在最坏的情况下（即初始序列完全逆序），需要进行n(n-1)/2次比较和3n(n-1)/2次移动，时间复杂度为O(n^2)。在最好的情况下（即初始序列已经有序），时间复杂度为O(n)，但这种情况较为罕见。

‌空间复杂度‌：冒泡排序是一种就地排序算法，不需要额外的存储空间，因此空间复杂度为O(1)。

‌稳定性‌：冒泡排序是一种稳定的排序算法，即相同元素的相对位置不会改变。

‌适用场景‌：由于冒泡排序的时间复杂度较高，它适用于数据量较小的情况。对于大量数据的排序，效率较低。

‌算法原理‌：冒泡排序通过重复遍历待排序的数列，比较两个相邻的元素，如果它们的顺序错误就交换过来。遍历工作是重复进行的，直到没有再需要交换的元素为止。

‌优化方法‌：可以通过设置一个标志位来优化冒泡排序。如果在一次完整的遍历中没有发生交换，说明数组已经有序，可以直接结束排序过程。这种方法可以在某些情况下将时间复杂度降低到O(n)。

六、冒泡排序优点

1‌、 实现简单‌：冒泡排序的算法逻辑非常简单，容易理解和实现。它只需要通过重复遍历要排序的数列，比较相邻元素的值，并在必要时交换它们的位置。

‌2、代码简洁‌：冒泡排序的代码非常简洁，不需要复杂的操作和额外的存储空间。

3‌、原地排序‌：冒泡排序是一种原地排序算法，不需要额外的内存空间来存储排序结果。它直接在原始数组上进行元素的比较和交换操作。

4‌、稳定性‌：冒泡排序是一种稳定的排序算法，即相等元素的相对顺序在排序前后保持不变。只有当两个相邻元素进行交换时才会改变它们的相对顺序。

5‌、适用于小规模数据‌：在数据规模较小的情况下，冒泡排序的性能还是可以接受的。对于小规模的数据集，冒泡排序可能比其他复杂的排序算法更快。

七、冒泡排序的缺点‌

 1、时间复杂度高‌：冒泡排序的时间复杂度为O(n^2)，在数据量较大时效率较低，尤其是当数据完全逆序时，时间复杂度达到O(n^2)。

 2‌、不适合大规模数据‌：由于其较高的时间复杂度，冒泡排序不适合处理大规模数据集。