经典算法之美：冒泡排序的优雅实现

基本概念

冒泡排序是一种简单的排序算法，通过重复比较相邻的元素并交换它们的位置来实现排序。它的名称来源于较小的元素像气泡一样逐渐“浮”到数组的顶端。

工作原理

介绍

冒泡排序是交换排序的一种，了解其基本思想对学习这种算法至关重要。

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。重复这个过程直到整个数组有序。

具体实现

以该数组为例，我们每次只关注相邻两个元素的大小关系

1. 我们先关注3和44，很明显，此时的数组[3，44]是有序的，无需交换
   

2. 此时，44和38需要交换
   
   
   此时数组[3，38，44]有序，从44的位置继续向后比较

3. 找到44和5时同理，需要交换44和5保证升序顺序
   
   
   你可能疑问？此时数组[3，38，5，44]不是有序的！
   不要紧，我们先继续往后交换

4. 我们省略几步，直接来看这趟比较的结束状态
   
   此时我们发现，数组中最大的元素47来到了最后面，这就是单趟冒泡排序的效果，一次选出数组中最大或最小的一个数放到应该在的位置上。

5. 我们来分析此时的数组
   
   数组被红线分割，红线左边为无序区，右边为有序区。
   此时的效果可能不明显，我们再模拟几次交换
   
   目前我们又执行了两次交换，可以看到：有序区的在增加，无序区在减少
   意识到这点之后，你就已经明白了冒泡排序的原理了：通过重复遍历无序区，对相邻元素依次比较并交换逆序对，使当前无序区的最值逐步‘浮’到其最终位置；每轮结束后，无序区长度减 1；直至无序区仅剩 1 个元素时，数组完全有序。

代码实现

因为冒泡排序是较为简单的经典排序算法，我们直接来看代码实现。

void BubbleSort(int arr[], int n)
{
	if (n <= 1) return;

	int i, j;
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 0; j < i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(arr[j], arr[j + 1]);
			}
		}
	}
}

最坏情况：数组完全逆序，需要进行 n(n-1)/2 次比较和交换，时间复杂度O(N^2)

此时可以对冒泡排序做出优化

void BubbleSort(int arr[], int n)
{
	if (n <= 1) return;

	int i, j;
	for (int i = n - 1; i >= 0; i--)
	{
		bool flag = false;

		for (int j = 0; j < i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(arr[j], arr[j + 1]);
				flag = true;
			}
		}

		if (flag == false)
			break;
	}
}

通过提前终止优化，如果在某次循环中没有发生元素交换，代表此时数组已经有序，直接退出。此时为最优情况，仅需一次遍历，时间复杂度为 O(N)

总结

冒泡排序是入门级排序算法，核心是通过相邻元素比较交换，让最值逐步 “浮” 到对应位置，随无序区收缩实现有序。​
其时间复杂度为 O (n²)（优化后最好情况 O (n)），空间复杂度 O (1)，是稳定排序。优势在于简单易实现，适配接近有序数据；但效率偏低，仅适合小规模场景。​
虽被高效算法替代，但其迭代逻辑仍是理解排序本质的基础