C++ 实现优化选择排序：从大到小排列输入整数

💻以下是使用 C++ 实现优化后的选择排序，将输入的 `n` 个数从大到小排序的代码： ```cpp #include <iostream> using namespace std; // 函数用于交换两个整数的值 void swap(int &a, int &b) { int temp = a; a = b; b = temp; } // 优化后的选择排序函数，从大到小排序 void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { // 假设当前位置的元素是最大值 int maxIndex = i; // 从 i+1 到 n-1 寻找更大的元素 for (int j = i + 1; j < n; ++j) { if (arr[j] > arr[maxIndex]) { // 如果找到更大的元素，更新最大值的索引 maxIndex = j; } } // 如果最大值的索引不是当前位置 i，交换它们 if (maxIndex != i) { swap(arr[i], arr[maxIndex]); } } } int main() { int n; // 读取输入的整数 n，表示元素的数量 cin >> n; int arr[100]; // 读取 n 个整数到数组中 for (int i = 0; i < n; ++i) { cin >> arr[i]; } // 调用选择排序函数对数组进行排序 selectionSort(arr, n); // 输出排序后的数组元素，元素之间用空格分隔 for (int i = 0; i < n; ++i) { if (i > 0) { cout << " "; } cout << arr[i]; } cout << endl; return 0; } ``` ### 代码详细解释： #### 1. `swap` 函数 ```cpp void swap(int &a, int &b) { int temp = a; a = b; b = temp; } ``` - 该函数用于交换两个整数的值。通过引用传递参数，确保在函数内部对参数的修改会影响到原始变量。 #### 2. `selectionSort` 函数 ```cpp void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { int maxIndex = i; for (int j = i + 1; j < n; ++j) { if (arr[j] > arr[maxIndex]) { maxIndex = j; } } if (maxIndex != i) { swap(arr[i], arr[maxIndex]); } } } ``` - **外层循环**：`for (int i = 0; i < n - 1; ++i)` 控制排序的轮数，总共需要进行 `n - 1` 轮排序。每一轮排序都会确定一个当前未排序部分的最大值，并将其放到正确的位置。 - **内层循环**：`for (int j = i + 1; j < n; ++j)` 用于在未排序的部分中寻找最大值的索引。从 `i + 1` 开始遍历到数组末尾，比较每个元素与当前最大值的大小，如果找到更大的元素，更新 `maxIndex`。 - **交换操作**：如果 `maxIndex` 不等于当前的 `i`，说明找到了更大的元素，调用 `swap` 函数交换 `arr[i]` 和 `arr[maxIndex]` 的位置。 #### 3. `main` 函数 ```cpp int main() { int n; cin >> n; int arr[100]; for (int i = 0; i < n; ++i) { cin >> arr[i]; } selectionSort(arr, n); for (int i = 0; i < n; ++i) { if (i > 0) { cout << " "; } cout << arr[i]; } cout << endl; return 0; } ``` - **输入部分**：首先读取一个整数 `n`，表示输入元素的数量。然后使用 `for` 循环读取 `n` 个整数到数组 `arr` 中。 - **排序部分**：调用 `selectionSort` 函数对数组进行排序。 - **输出部分**：使用 `for` 循环遍历排序后的数组，输出每个元素，元素之间用空格分隔。最后输出换行符。 ### 复杂度分析： - **时间复杂度**：选择排序的时间复杂度始终为 $O(n^2)$，因为无论输入数据的初始状态如何，都需要进行两层嵌套的循环。 - **空间复杂度**：$O(1)$，只使用了常数级的额外空间，主要用于存储临时变量。 ######[AI问答 | 1176点数解答 | 2026-04-11 19:30:42]