数学结构学习之冒泡排序（含C++代码）

淡淡的烟草味﹌ 2024-04-18 22:55 34阅读 0赞

# **1.数学结构学习之冒泡排序（含C++代码）** #

## 1.1 原理 ##

**对于一个未排序的序列，从前向后依次检查每一对相邻元素，一旦发现逆序即交换二者的位置。对于长度为n的序列，共需做n - 1 次比较和不超过n - 1次交换。交换过程的原理如下图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70][]

**多数的 这类交换操作，都会使得越小（大）的元素朝上（下）方移动，直至它们抵达各 自应处的位置。 排序过程中，所有元素朝各自最终位置亦步亦趋的移动过程，犹如气泡在水中的上下沉浮， 冒泡排序（bubblesort）算法也因此得名。**

## **1.2 时间复杂度** ##

**       bubblesort1A()算法由内、外两层循环组成。内循环从前向后，依次比较各对相邻元素， 如有必要则将其交换。故在每一轮内循环中，需要扫描和比较n - 1对元素，至多需要交换n - 1 对元素。元素的比较和交换，都属于基本操作，故每一轮内循环至多需要执行2(n - 1)次基本 操作。另外，外循环至多执行n - 1轮。因此，总共 需要执行的基本操作不会超过2(n - 1)2次。若以此来度量该算法的时间复杂度，则有 T(n) = O(2(n-1)2 ) 根据大O记号的性质，可进一步简化和整理为： T(n) = O(2n2 - 4n + 2) = O(2n^2 ) = O(n^2 )**

### 1.3 冒泡排序算法源代码 ###

#include <iostream>
    using namespace std;
    //C++版冒泡排序算法 
    void bubblesort1A(int A[], int n) { //
    	bool sorted = false; //整体排序标志，首先假定尚未排序
    	int m = n;
    	while (!sorted) { 
    		sorted = true; //假定已经排序
    		for (int i = 1; i < n; i++) { //自左向右逐对检查弼前范围A[0, n)内癿各相邻元素
    			if (A[i - 1] > A[i]) { //一旦A[i - 1]不A[i]逆序，则
    				int temp = A[i - 1];
    				A[i-1] = A[i];
    				A[i] = temp;
    				
    				sorted = false; //因整体排序丌能保证，需要清除排序标志
    			}
    		}
    		n--; //至此末元素必然就位，故可以缩短待排序序列癿有效长度
    	}
    	for(int i = 0; i < m; i++){
    		//C++中的输出语法 
    		cout <<"A中第" <<i+1<<"个元素" << A[i] << endl;
    	}
    } 
    //程序运行主函数 
    int main(){
    	int A[] = {2,9,3,6,1,17,43,21,32,5,78,54}; 
    	int n = 12;
    	bubblesort1A(A,n);
    }

**程序运行结果如图**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/162b58072a644108ad6bcdf7c3585fd3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzA2ODc4_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1b452ff47952456f8a37fdb9ae47505b.png