冒泡排序（Bubble Sort）是一种简单的排序算法，它的基本思想是重复地遍历待排序的列表，一次比较相邻的两个元素，如果它们的顺序不正确，就交换它们，直到没有任何交换发生。这个过程会一遍又一遍地重复，直到整个列表已经排序完成。冒泡排序的名称来自于排序过程中较小的元素会像”气泡”一样逐渐上浮到数组的开头。

1. 算法思路

1. 从数组的第一个元素开始，比较它与下一个元素。
2. 如果当前元素大于下一个元素，就交换它们的位置，使较大的元素向右移动。
3. 继续比较下一个元素，重复步骤2，直到达到数组的末尾。这个过程会让数组中最大的元素沉底，类似气泡一样逐渐上浮到数组的最后。
4. 重复步骤1-3，但是不再考虑已经排好序的最后一个元素（因为它已经是最大的），继续向前的元素进行比较和交换，直到整个数组有序。

2. 优化分析

冒泡排序是一种简单但效率较低的排序算法。虽然它的时间复杂度为 \(O(n^{2})\)，但可以通过一些优化来减少比较和交换的次数。

冒泡排序的基本实现会在每一轮遍历中不管数组是否已经有序，都会进行完整的遍历。可以通过添加一个标志来检查是否在某一轮中发生了交换。如果没有发生交换，表示数组已经有序，可以提前退出循循环。

3. 代码实现

3.1 C++ 实现

#include <iostream>
#include <random>
#include <array>
using namespace std;

#define ARR_LEN 10
void bubble_sort(array<int, ARR_LEN> &arr)
{	
	int temp;
	for (int i = 0; i < arr.size() - 1; ++ i)
	{
		// 假设已经完全有序
		bool flag = true;
		for (int j = 0; j < arr.size()- i - 1; ++j)
		{	
			// 降序
			if (arr[j + 1] > arr[j])
			{
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
				// 说明尚未完全有序
				flag = false;
			}
		}

		if (flag)
		{
			break;
		}
	}
}

void print_array(array<int, ARR_LEN> my_array)
{
	for (int i = 0; i < my_array.size(); ++i)
		cout << my_array[i] << " ";
	cout << endl;
}


int main()
{
	// 随机种子设备
	random_device seed;
	// 随时数生成器
	mt19937 generator(seed());
	// 均匀分布
	uniform_int_distribution<int> random(10, 20);

	// 生成随机数组
	array<int, ARR_LEN> my_array = { 0 };
	for (int i = 0; i < my_array.size(); ++i)
		my_array[i] = random(generator);

	print_array(my_array);
	bubble_sort(my_array);
	print_array(my_array);

	return 0;
}

13 10 20 20 11 20 13 11 14 18
20 20 20 18 14 13 13 11 11 10

3.2 Python 实现

import random


def bubble_sort(arr):
    temp = 0
    for i in range(0, len(arr) - 1):
        # 假设已经完全有序
        flag = True
        for j in range(0, len(arr) -i - 1):
            if arr[j + 1] > arr[j]:
                temp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = temp
                # 如果进行交换，说明尚未完全有序
                flag = False
        if flag:
            break


if __name__ == '__main__':
    arr = [random.randint(0, 10) for _ in range(10)]
    print(arr)
    bubble_sort(arr)
    print(arr)

[8, 0, 2, 10, 8, 3, 3, 5, 7, 5]
[10, 8, 8, 7, 5, 5, 3, 3, 2, 0]

4. 复杂度分析

冒泡排序通过多次比较和交换相邻元素来将较大（或较小）的元素逐渐“冒泡”到数组的末尾（或开头），以达到排序的目的。

时间复杂度：

• 最好情况时间复杂度：O(n) – 当输入数组已经有序，不需要进行任何交换。
• 平均情况时间复杂度：O(n^2) – 平均情况下，需要进行多次遍历和元素交换。
• 最坏情况时间复杂度：O(n^2) – 当输入数组逆序排列时，需要进行最大数量的比较和交换。

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

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

尽管冒泡排序具有容易实现和理解的优点，但它的效率较低，尤其在大型数据集上。由于最坏情况下需要进行O(n^2)次比较和交换，因此不适合处理大规模数据。冒泡排序在教学和理解排序算法的概念时有用，但在实际应用中很少被使用。