C++实现简单选择排序详解及代码示例

**C++实现选择排序** 选择排序是一种简单直观的排序算法，它通过反复遍历待排序的元素序列，每次从未排序的部分中找到最小（或最大）的元素，然后将其放到已排序序列的末尾。这种算法的时间复杂度为O(n^2)，适用于小型数据集或者教育目的中的教学演示，因为它易于理解和实现。 以下是C++语言中选择排序的详细解释与实现： ### 选择排序算法步骤 1. **初始化**：定义一个`selectionSort`函数，它接受一个整数数组`arr`和数组的长度`n`作为参数。 2. **找到最小元素**： - 使用两个嵌套循环：外层循环控制未排序部分的开始（`i`从0到`n-2`），内层循环遍历剩余未排序的元素（`j`从`i+1`到`n-1`）。 - 在内层循环中，如果`arr[j]`小于当前未排序部分的最小元素`arr[minIndex]`，则更新`minIndex`为`j`，因为找到了更小的元素。 3. **交换元素**： - 当内层循环结束后，将`arr[minIndex]`与`arr[i]`的位置进行交换，这样每次外层循环结束时，已排序部分的最后一个元素都是未排序部分中的最小值。 4. **重复过程**：外层循环继续进行，直到所有元素都被放置在正确的位置，即整个数组有序。 ### C++代码详解 ```cpp // 包含iostream库以便使用标准输入输出 #include<iostream> // 引入命名空间std，避免函数重名冲突 using namespace std; // 定义选择排序函数 void selectionSort(int arr[], int n) { int i, j, minIndex, temp; // 外层循环遍历数组 for (i = 0; i < n - 1; i++) { // 初始化minIndex为当前索引 minIndex = i; // 内层循环寻找未排序部分的最小值 for (j = i + 1; j < n; j++) { // 如果找到更小的元素，更新minIndex if (arr[j] < arr[minIndex]) { minIndex = j; } } // 交换找到的最小值与当前位置的元素 temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } // 主函数 int main() { // 创建一个整数数组并初始化 int arr[] = {64, 25, 12, 22, 11}; int n = sizeof(arr) / sizeof(arr[0]); // 调用selectionSort函数对数组进行排序 selectionSort(arr, n); // 输出排序后的数组 cout << "排序后的数组："; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; return 0; } ``` 总结起来，C++实现的选择排序算法通过逐个找到剩余元素中的最小值并将其插入已排序部分，实现了对整数数组的升序排列。尽管其效率不高，但它清晰地展示了基本的排序算法原理，适用于学习和理解排序算法的基础概念。