冒泡排序（详解）c++

news/2025/2/24 13:31:53

冒泡排序(Bubble Sort)也是⼀种简单的排序算法。它的⼯作原理是每次检查相邻两个元素，如果前⾯的元素与后⾯的元素满⾜给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。由于在算法的执⾏过程中，较⼤的元素像是⽓泡般慢慢浮到数列的末端，故叫做冒泡排序

算法思想：

执行 n-1 趟操作，每趟从前往后比较待排序区间的相邻元素如果逆序，就交换。
每趟结束之后，就会有一个较大元素在最终的位置上。

代码实现：

代码测试：P1177 【模板】排序 - 洛谷

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

void bubble_sort()
{
	// 依次枚举待排序区间的最后一个元素
	for (int i = n; i > 1; --i)  //n-1趟后，第一个也变得有序了
	{
		//[1, i] 就是待排序区间
		for (int j = 1; j <= i; ++j) //当前位置和下一个位置作比较，如果<=i就会和i+1位置作比较,比如排序1 2，结果是0 1
		{
			if (a[j] > a[j + 1])
			{
				swap(a[j], a[j + 1]);
			}
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];

	bubble_sort();

	for (int i = 1; i <= n; ++i) cout << a[i] << " ";
	cout << '\n';

	return 0;
}

优化

当某一趟冒泡操作中，没有执行元素的交换操作时，整个序列就是有序的了没有必要再继续执行冒泡排序算法了，比如1 2 3 4 5 9 8 7 执行了两趟冒泡排序后变成1 2 3 4 5 6 7 8 9升序，此时已是有序序列没有再遍历排序了

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

void bubble_sort()
{
	// 依次枚举待排序区间的最后一个元素
	for (int i = n; i > 1; --i)  //n-1趟后，第一个也变得有序了
	{
		bool flag = true;
		//[1, i] 就是待排序区间
		for (int j = 1; j < i; ++j) //当前位置和下一个位置作比较，如果<=i就会和i+1位置作比较,比如排序1 2，结果是0 1
		{
			if (a[j] > a[j + 1])
			{
				swap(a[j], a[j + 1]);
				flag = false;
			}
		}
        //遍历一趟下来发现已是有序序列
		if (flag) return; 
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];

	bubble_sort();

	for (int i = 1; i <= n; ++i) cout << a[i] << " ";
	cout << '\n';

	return 0;
}