排序算法：冒泡排序

冒泡排序是一种简单的排序算法，其基本思想是通过比较相邻元素的大小，依次交换相邻元素的位置，将最大（或最小）的元素逐步“冒泡”到序列的最后（或最前）位置。具体实现过程如下：

1. 从序列的第一个元素开始，依次比较相邻的两个元素，如果前一个元素比后一个元素大，则交换它们的位置；

2. 继续比较下一组相邻元素，直到将最大的元素“冒泡”到序列的最后位置；

3. 重复上述步骤，直到整个序列都有序为止。

下面是一个简单的 C++ 实现：

void bubbleSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 如果没有交换，说明已经有序，直接退出
    }
}

在上面的代码中，变量 swapped 用来标记在一轮比较中是否有元素交换的操作，如果没有交换，说明序列已经有序，可以直接退出循环。

冒泡排序的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。由于其简单、易于实现，冒泡排序在一些简单场景下仍然有一定的应用价值。但是，对于大规模的数据排序，冒泡排序的效率远远低于其他高效的排序算法，比如快速排序和归并排序。

下面通过一个例子来演示冒泡排序的过程。

假设我们有一个需要排序的数组：[4, 2, 6, 1, 3, 5]，现在来演示一下冒泡排序的过程。

第一轮比较：

首先比较 4 和 2，因为 4 > 2，所以交换它们的位置，数组变成 [2, 4, 6, 1, 3, 5]。

接着比较 4 和 6，因为 4 < 6，所以不交换它们的位置，数组不变。

继续比较 6 和 1，因为 6 > 1，所以交换它们的位置，数组变成 [2, 4, 1, 6, 3, 5]。

接着比较 6 和 3，因为 6 > 3，所以交换它们的位置，数组变成 [2, 4, 1, 3, 6, 5]。

最后比较 6 和 5，因为 6 > 5，所以交换它们的位置，数组变成 [2, 4, 1, 3, 5, 6]。

第一轮比较结束，此时数组的最后一个元素已经是最大的了，所以可以不再比较它，只需要比较前面的元素即可。

第二轮比较：

首先比较 2 和 4，因为 2 < 4，所以不交换它们的位置，数组不变。

接着比较 4 和 1，因为 4 > 1，所以交换它们的位置，数组变成 [2, 1, 4, 3, 5, 6]。

接着比较 4 和 3，因为 4 > 3，所以交换它们的位置，数组变成 [2, 1, 3, 4, 5, 6]。

最后比较 4 和 5，因为 4 < 5，所以不交换它们的位置，数组不变。

第二轮比较结束，此时数组的最后两个元素已经是最大的了，所以可以不再比较它们，只需要比较前面的元素即可。

第三轮比较：

首先比较 2 和 1，因为 2 > 1，所以交换它们的位置，数组变成 [1, 2, 3, 4, 5, 6]。

接着比较 2 和 3，因为 2 < 3，所以不交换它们的位置，数组不变。

最后比较 3 和 4，因为 3 < 4，所以不交换它们的位置，数组不变。

第三轮比较结束，此时数组已经有序，排序完成。

冒泡排序的时间复杂度为 O(n^2)，其中 n 为待排序数组的长度。这是因为，冒泡排序需要进行 n-1 轮比较，每轮比较需要比较 n-i 次，其中 i 表示已经排序好的元素个数。

冒泡排序的空间复杂度为 O(1)，因为它只需要常数级别的额外空间来存储一些中间变量。

由于冒泡排序的时间复杂度较高，因此在实际应用中并不常用，更常用的是其他的排序算法，比如快速排序、归并排序、堆排序等等。但是由于冒泡排序的思想简单易懂，可以帮助初学者更好地理解排序算法的思想，因此它常常被作为排序算法的入门练习。

下面是一个完整的 C++ 代码演示冒泡排序：

#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

上述代码中，我们定义了一个 bubbleSort 函数来实现冒泡排序，该函数的参数包括待排序数组 arr 和数组的长度 n。在函数内部，我们使用两个嵌套的循环来实现冒泡排序，外层循环控制需要进行的比较轮数，内层循环用于比较相邻的元素并交换它们的位置。

在 main 函数中，我们定义了一个整型数组 arr，并使用 sizeof 运算符和数组元素的类型大小来计算数组的长度。然后，我们调用 bubbleSort 函数对数组进行排序，并输出排序结果。

注意，在上述代码中，我们使用了 swap 函数来交换数组中两个元素的位置。C++ 中的 swap 函数可以用于交换任意类型的值，包括整型、浮点型、字符型、字符串等等。