C++优化冒泡排序实现从大到小排序

### 🍭思路分析 冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。为了优化冒泡排序，我们可以设置一个标志位，当某一轮没有发生交换时，说明数组已经有序，可以提前结束排序。 ### 🔧代码实现 ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; int arr[100]; for (int i = 0; i < n; i++) { cin >> arr[i]; } // 优化后的冒泡排序 bool swapped; for (int i = 0; i < n - 1; i++) { swapped = false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] < arr[j + 1]) { // 交换 arr[j] 和 arr[j+1] int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = true; } } // 如果没有发生交换，说明数组已经有序，提前结束排序 if (!swapped) { break; } } // 输出排序后的数组 for (int i = 0; i < n; i++) { if (i > 0) { cout << " "; } cout << arr[i]; } cout << endl; return 0; } ``` ### 📝代码解释 1. **输入处理**：首先读取一个整数 `n`，表示数组的长度。然后读取 `n` 个整数，存储在数组 `arr` 中。 2. **优化的冒泡排序**： - 使用一个布尔变量 `swapped` 来记录每一轮是否发生了交换。 - 外层循环控制排序的轮数，最多进行 `n - 1` 轮。 - 内层循环比较相邻的元素，如果顺序错误则交换它们，并将 `swapped` 设置为 `true`。 - 如果某一轮没有发生交换，说明数组已经有序，提前结束排序。 3. **输出结果**：遍历排序后的数组，输出每个元素，相邻元素之间用空格隔开。 ### 🚀复杂度分析 - **时间复杂度**：平均情况下为 $O(n^2)$，但在数组已经有序的情况下，时间复杂度可以优化到 $O(n)$。 - **空间复杂度**：$O(1)$，只使用了常数级的额外空间。 ######[AI写代码神器 | 632点数解答 | 2026-03-20 19:46:45]