C++冒泡排序从大到小并去重实现与详解

好的，这是一个经典的排序与去重问题。下面我给出 **C++** 的实现，并使用 **冒泡排序** 从大到小排序，同时在排序过程中或排序后去重。 ## 🧭 解题思路 1. **读取输入**：第一行是整数 `n`，第二行是 `n` 个整数。 2. **冒泡排序（从大到小）**： - 外层循环 `i` 从 0 到 n-2，内层循环 `j` 从 0 到 n-i-2。 - 如果 `arr[j] < arr[j+1]`，则交换，将较小的数沉到后面，较大的数浮到前面。 3. **去重**： - 排序后，重复元素相邻。我们可以在排序后遍历，只输出第一次出现的元素（与上一个不同时输出）。 - 也可以在排序过程中去重，但更推荐排序后统一去重，代码更清晰。 ## 💻 C++ 代码实现 ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; int arr[100]; // 题目 n < 100 // 读取 n 个整数 for (int i = 0; i < n; i++) { cin >> arr[i]; } // 冒泡排序（从大到小） for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j] < arr[j + 1]) { // 交换 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } // 去重并输出 bool first = true; for (int i = 0; i < n; i++) { // 跳过与前一个相同的元素（从第二个开始判断） if (i > 0 && arr[i] == arr[i - 1]) { continue; } if (!first) { cout << " "; } cout << arr[i]; first = false; } cout << endl; return 0; } ``` ## 📝 代码解释 - **变量 `n`**：存储数字个数。 - **数组 `arr[100]`**：固定大小，因为 `n < 100`，所以足够。 - **冒泡排序外层循环**：控制总共需要比较的轮数（n-1 轮）。 - **冒泡排序内层循环**：每轮比较相邻元素，若前者小于后者则交换，实现从大到小。 - **去重逻辑**：排序后，重复元素会相邻。遍历时，如果当前元素等于前一个元素（`i > 0` 且相等），则跳过输出。 ## 🧪 测试样例 输入： ``` 8 3 3 2 7 7 7 6 8 ``` 输出： ``` 8 7 6 3 2 ``` 符合要求。 ## ⚠️ 注意事项与优化建议 - **数组大小**：这里固定为 100，但更安全的方式是使用 `vector<int>` 动态分配，防止溢出。 - **时间复杂度**：冒泡排序为 O(n²)，对于 n<100 足够快，但若 n 较大（如 10⁵）则建议用 `sort` 或 `unique`。 - **去重方法**：也可以使用 `std::sort` + `std::unique`，代码更简洁，但本题目明确要求冒泡排序，所以这里手动实现。 - **边界情况**：当 n=1 时，不进入排序循环，直接输出该数，功能正确。 ## 🌐 进阶扩展（高效解法参考） 如果题目不强制冒泡排序，可以这样写（C++ STL）： ```cpp #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> v(n); for (int i = 0; i < n; i++) cin >> v[i]; sort(v.begin(), v.end(), greater<int>()); // 从大到小 v.erase(unique(v.begin(), v.end()), v.end()); // 去重 for (size_t i = 0; i < v.size(); i++) { if (i) cout << " "; cout << v[i]; } cout << endl; return 0; } ``` 这种方法时间复杂度 O(n log n)，且代码简洁，适合通用场景。 --- **开发建议**： - 考试或作业若要求用冒泡，务必按题目要求写，但理解 STL 方法也很重要。 - 注意数组越界和数组大小声明，避免使用魔法数字，可以定义常量。 - 代码风格要清晰，加注释，便于复查。 ######[AI写代码神器 | 1103点数解答 | 2026-08-28 19:08:35]