冒泡排序是C++中一种基础但重要的排序算法，它通过不断比较和交换相邻元素来将较大的元素逐步"浮"到数组末端。下面我将为你介绍几种不同的实现方法、优化技巧，并提供代码实例。

冒泡排序的基本原理

冒泡排序的核心思想是重复地遍历待排序序列，依次比较相邻的两个元素，如果它们的顺序错误（例如前一个大于后一个）就交换它们。这项工作重复进行，直到没有再需要交换的元素，此时数列便排序完成。这个过程中，较大的元素会逐渐从序列中"浮"到末尾，就像水中的气泡一样，故名"冒泡排序"。

基础实现方法

这是最直接的冒泡排序实现，使用两层嵌套循环。

思路：

• 外层循环：控制排序的轮数，每完成一轮，当前未排序部分的最大元素就会"冒"到正确位置。
• 内层循环：负责在每一轮中进行相邻元素的比较和交换。注意每轮比较的范围会随着已排序元素的增加而减小。

代码实例：

#include <iostream>
using namespace std;

void bubbleSortBasic(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]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度

    bubbleSortBasic(arr, n);

    cout << "排序后的数组: \n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

输出：

排序后的数组: 
11 12 22 25 34 64 90

优化实现：提前终止

基础版本即使数组已有序也会继续遍历。我们可以通过一个标志位检查某一轮是否发生了交换，若没有交换则说明数组已有序，可提前终止排序。

思路：

• 在每一轮内层循环开始前，设置一个标志（如 “swapped”）为 “false”。
• 如果该轮中发生了元素交换，则将"swapped" 置为 “true”。
• 每轮结束后检查 “swapped”，如果仍为 “false”，说明数组已有序，可立即退出循环。

代码实例：

#include <iostream>
using namespace std;

void bubbleSortOptimized(int arr[], int n) {
    // 外层循环控制排序轮数
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false; // 标记本轮是否发生交换
        // 内层循环执行相邻元素的比较和交换
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 使用std::swap进行交换
                swap(arr[j], arr[j + 1]);
                swapped = true; // 发生交换，标记为true
            }
        }
        // 如果本轮没有发生任何交换，说明数组已经有序，提前结束
        if (!swapped) {
            break;
        }
    }
}

// main函数与基础实现相同
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSortOptimized(arr, n);

    cout << "排序后的数组 (优化版): \n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

模板化实现：支持多种数据类型

利用C++的模板，我们可以编写一个通用的冒泡排序函数，使其不仅能排序整数数组，还能排序浮点数、字符等其他基本数据类型的数组。

思路：

• 使用
  "template " 声明一个模板函数，
  “T” 代表泛型类型。
• 函数体内的比较和交换操作均使用类型
  “T”。

代码实例：

#include <iostream>
using namespace std;

// 使用模板支持多种数据类型
template <typename T>
void bubbleSortTemplate(T arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) { // 要求类型T支持>运算符
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

int main() {
    // 排序整型数组
    int intArr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(intArr) / sizeof(intArr[0]);
    bubbleSortTemplate(intArr, n);
    cout << "排序后的整型数组: ";
    for (int i = 0; i < n; i++) cout << intArr[i] << " ";
    cout << endl;

    // 排序浮点型数组
    float floatArr[] = {3.14f, 1.41f, 2.71f, 1.61f, 2.72f};
    int m = sizeof(floatArr) / sizeof(floatArr[0]);
    bubbleSortTemplate(floatArr, m);
    cout << "排序后的浮点型数组: ";
    for (int i = 0; i < m; i++) cout << floatArr[i] << " ";

    return 0;
}

更多优化方向

除了提前终止，还有一些思路可以进一步优化冒泡排序的性能：

• 记录最后交换位置：在每轮扫描中，记录最后一次发生交换的位置。这个位置之后的元素显然已经有序，下一轮循环时只需比较到这个位置即可。
• 双向冒泡（鸡尾酒排序）：排序过程像钟摆一样，第一轮从左到右比较交换，第二轮从右到左比较交换，如此往复。对于大部分已排序或部分特殊情况的数组，效率更高。

总结与选择

特性/方法	基础实现	优化实现 (提前终止)	模板化实现
核心思想	两层循环遍历比较	增加交换标志位，若某轮无交换则提前终止	使用模板，支持多种数据类型
时间复杂度（平均）	O(n²)	O(n²)，但对已有序序列最优情况为O(n)	O(n²)，最优情况O(n)
空间复杂度	O(1)	(原地排序) O(1)	O(1)
稳定性	稳定 (相等元素不改变相对顺序)	稳定	稳定
适用场景	教学理解	小规模数据或可能部分有序的数据	需要排序多种基本数据类型的小规模数据集

总的来说：

• 对于初学者，先从基础实现理解冒泡排序的双循环核心机制。
• 在实际应用中，优化实现（提前终止） 通常是更明智的选择，因为它能避免在数组已有序时进行不必要的循环。
• 如果你需要排序不同基本数据类型的数组，模板化实现提供了很好的灵活性。

冒泡排序虽然在处理大规模数据时效率不高（时间复杂度为O(n²)），但其算法简单稳定，是理解排序概念和双循环结构的良好起点。对于小规模数据或对性能要求不极端的场景，它仍然是一个可选方案。