C++优化选择排序实现从大到小排序

### 🔍思路分析 选择排序的基本思想是在未排序序列中找到最大（小）元素，存放到排序序列的起始位置。优化后的选择排序可以在每一轮同时找到最大和最小元素，分别放到未排序序列的两端，从而减少比较次数。 ### 💻代码实现 ```cpp #include <iostream> #include <vector> using namespace std; // 优化后的选择排序函数，从大到小排序 void optimizedSelectionSort(vector<int>& arr) { int left = 0, right = arr.size() - 1; while (left < right) { int maxIndex = left; int minIndex = right; for (int i = left; i <= right; i++) { if (arr[i] > arr[maxIndex]) { maxIndex = i; } if (arr[i] < arr[minIndex]) { minIndex = i; } } // 交换最大元素到左边 swap(arr[left], arr[maxIndex]); // 如果最小元素的位置刚好是原来最大元素的位置，修正最小元素的位置 if (minIndex == left) { minIndex = maxIndex; } // 交换最小元素到右边 swap(arr[right], arr[minIndex]); left++; right--; } } int main() { int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } optimizedSelectionSort(arr); for (int i = 0; i < n; i++) { if (i > 0) { cout << " "; } cout << arr[i]; } cout << endl; return 0; } ``` ### 📝代码解释 1. **`optimizedSelectionSort`函数**： - 使用两个指针`left`和`right`分别指向未排序序列的左右两端。 - 在每一轮中，同时找到最大和最小元素的索引`maxIndex`和`minIndex`。 - 先将最大元素交换到`left`位置，再将最小元素交换到`right`位置。 - 每一轮结束后，`left`指针右移，`right`指针左移。 2. **`main`函数**： - 读取输入的整数`n`和`n`个整数，存储在`vector`中。 - 调用`optimizedSelectionSort`函数对数组进行排序。 - 输出排序后的数组，相邻元素用空格隔开。 ### ⚙️复杂度分析 - **时间复杂度**：$O(n^2)$，因为需要进行两轮嵌套的循环。 - **空间复杂度**：$O(1)$，只使用了常数级的额外空间。 ### 🚀开发建议 - **边界条件检查**：在实际应用中，需要对输入的`n`进行有效性检查，确保`1 < n < 100`。 - **错误处理**：可以添加输入错误处理，例如输入非整数的情况。 - **代码复用**：将排序函数封装成独立的模块，方便在其他项目中复用。 ######[AI写代码神器 | 776点数解答 | 2026-03-20 19:54:05]