优化冒泡排序实现 n 个数从大到小排序

以下是使用 C++ 实现的优化后的冒泡排序，将输入的 `n` 个数从大到小排序： ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; int a[100]; for (int i = 0; i < n; i++) { cin >> a[i]; } // 优化后的冒泡排序 bool swapped; for (int i = 0; i < n - 1; i++) { swapped = false; for (int j = 0; j < n - i - 1; j++) { if (a[j] < a[j + 1]) { // 交换元素 int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; swapped = true; } } // 如果某一轮没有发生交换，说明已经排好序，提前结束排序 if (!swapped) { break; } } // 输出排序后的数组 for (int i = 0; i < n; i++) { if (i > 0) { cout << " "; } cout << a[i]; } cout << endl; return 0; } ``` ### 代码解释： 1. **输入部分**：首先读取整数 `n`，表示输入数字的数量。然后使用循环读取 `n` 个整数并存储到数组 `a` 中。 2. **优化后的冒泡排序**： - 引入一个布尔变量 `swapped` 来标记每一轮是否发生了交换。 - 外层循环控制排序的轮数，最多进行 `n - 1` 轮。 - 内层循环用于比较相邻元素，如果前一个元素小于后一个元素，则交换它们的位置，并将 `swapped` 标记为 `true`。 - 每一轮结束后，检查 `swapped` 的值。如果为 `false`，说明这一轮没有发生交换，数组已经排好序，提前结束排序。 3. **输出部分**：使用循环遍历排序后的数组，将元素依次输出，相邻元素之间用空格隔开。 ### 复杂度分析： - **时间复杂度**：在最好情况下（数组已经有序），时间复杂度为 $O(n)$；在最坏情况下，时间复杂度为 $O(n^2)$。 - **空间复杂度**：$O(1)$，只使用了常数级的额外空间。 ######[AI问答 | 614点数解答 | 2026-04-11 19:26:36]