目录

一、算法介绍

1.算法思想

2.优化思路

3.算法流程

二、算法实现

1.代码实现​

2.测试用例及结果

三、性能分析

1.时间复杂度

2.空间复杂度

3.稳定性

---

一、算法介绍

1.算法思想

冒泡排序的基本思想就是通过两两比较相邻元素，将较大（或较小）的元素往后交换，这样每经过一趟交换，就可将当前序列中最大的元素交换到最后的位置，并且该元素不参与下一趟交换，这样经过n-1趟交换后，即可完成对序列的升序（或降序）排序。

2.优化思路

若序列本身是基本有序的状态，那么可能经过几趟交换后，序列就已经提前达到有序状态，但是次数算法并不会退出，它会固定的执行n-1趟，但是不会再发生元素位置交换，那么此时我们可以设置一个标志位，用来标记每趟冒泡内部是否发生元素交换，若没有发生，则说明序列已经提前达到有序状态，此时直接返回退出，从而一定程度上提高算法的效率。

3.算法流程

图片来源于网络

 每趟排序对相邻两个元素进行比较，将较大的元素往后交换，相同或小于则不会交换。每完成一趟排序，待排序序列长度减一，即上一趟排序交换到最后面的元素不参与下一趟排序。

二、算法实现

1.代码实现
​

#include<iostream>
using namespace std;

void BubbleSort(int* arr, int size) {
	for (int i = 0; i < size - 1; i++) {
		int flag = 1;//标记是否发生交换
		for (int j = 0; j < size - i - 1; j++) {//两两比较
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);//交换元素位置
				flag = 0;
			}
		}
		if (flag) {//提前达到有序
			return;
		}
	}
}

void PrintArr(int* arr, int size) {//数组打印
	for (int i = 0; i < size; i++) {
		cout << arr[i] << ' ';
	}
}

void Test() {
	int arr[] = { 2,5,4,8,7,1,3,9,6 };
	int size = sizeof(arr) / sizeof(arr[0]);

	cout << "排序前：";
	PrintArr(arr, size);
	BubbleSort(arr, size);
	cout << endl << "排序后：";
	PrintArr(arr, size);
	cout << endl;
}

int main() {
	Test();
	return 0;
}

2.测试用例及结果

测试用例：

arr[]={2,5,4,8,7,1,3,9,6}

测试结果：

三、性能分析

1.时间复杂度

最坏情况

根据算法排序思想可知，最坏情况即序列初始状态为逆序时，此时算法需要执行n-1趟，且每趟的相邻量元素都需要交换，所以最坏情况下的时间复杂度为。

最好情况

同样，最好情况即序列初始已经是有序状态，每趟都不需要发生交换，根据优化思路，只需要遍历一遍序列，发现没有发生元素交换，算法就会立刻退出返回，所以最好情况下的时间复杂度为O(n)。

平均情况

综合两种情况，冒泡排序的时间复杂度为。

2.空间复杂度

由于算法实现中只使用了几个临时变量作为标记，没有借助额外的辅助空间，所以空间复杂度为O(1)。

3.稳定性

​因为排序思想是对序列进行顺序遍历并两两比较，将较大的元素往后交换，相同时不会发生交换，所以不会改变相同元素的相对位置，所以冒泡排序是稳定的。

活动地址：CSDN21天学习挑战赛