C++如何实现冒泡排序算法？C++经典排序算法入门【数据结构】

冒泡排序是C++入门必学的排序算法，通过重复遍历数组、两两比较并交换相邻元素，使较大元素逐轮“浮”至末尾，实现升序排列；支持模板泛化，时间复杂度最坏O(n²)，最好O(n)，稳定且空间复杂度为O(1)。

冒泡排序是C++入门必学的排序算法，原理简单、逻辑清晰，适合理解排序的基本思想。它通过重复遍历待排序数组，比较相邻元素并交换位置，让较大（或较小）的元素像气泡一样逐渐“浮”到一端。

核心思路：两两比较，逐轮下沉

每一轮遍历中，从第一个元素开始，依次比较相邻两个数；如果顺序错误（比如升序时前一个比后一个大），就交换它们。这样每轮结束，当前未排序部分的最大值就会被“冒泡”到末尾。重复这个过程，直到没有交换发生，说明已排好序。

基础实现（升序排列）

以下是一个标准、易懂的C++实现：

  // 冒泡排序函数（升序）
  void bubbleSort(int arr[], int n) {
    for (int i = 0; i       bool swapped = false;                        // 优化：记录是否发生交换
      for (int j = 0; j         if (arr[j] > arr[j + 1]) {
          std::swap(arr[j], arr[j + 1]);
          swapped = true;
        }
      }
      if (!swapped) break;                         // 提前退出：已有序
    }
  }

关键细节与常见优化

• 边界控制：内层循环上限用 n - 1 - i，因为每轮后末尾 i 个元素已就位，无需再比
• 提前终止：引入 swapped 标志，若某轮无交换，说明整体已有序，直接退出
• 稳定性：冒泡排序是稳定排序——相等元素不会因交换而改变相对位置
• 时间复杂度：最坏/平均 O(n²)，最好（已排序）O(n)；空间复杂度 O(1)

扩展：支持任意类型（模板写法）

用模板泛化，让函数能处理 double、string 或自定义类（需支持 ）：

  template
  void bubbleSort(T arr[], int n) {
    for (int i = 0; i       bool swapped = false;
      for (int j = 0; j         if (arr[j] > arr[j + 1]) {
          std::swap(arr[j], arr[j + 1]);
          swapped = true;
        }
      }
      if (!swapped) break;
    }
  }

基本上就这些。掌握冒泡排序，不单是为了排序本身，更是为理解后续快排、归并等算法打下逻辑基础。