selection sort.zip

选择排序是一种简单的排序算法，它的基本思想是在未排序的序列中找到最小（或最大）的元素，存放到排序序列的起始位置，然后再从剩余未排序的元素中继续寻找最小（或最大）的元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。在C++中实现选择排序，我们可以使用标准模板库（STL）中的算法，也可以自定义函数来完成。 我们来讲解一下C++中如何自定义一个选择排序的函数。选择排序的时间复杂度为O(n^2)，其中n是待排序序列的长度。它不适用于大规模数据排序，但其简单性使得它在教学和理解排序算法时很有用。 ```cpp void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { // 找到未排序部分的最小元素索引 int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // 将找到的最小元素与当前位置的元素交换 std::swap(arr[i], arr[minIndex]); } } ``` 在这个函数中，我们首先遍历整个数组，假设当前元素是最小的。然后，我们在剩下的未排序部分中查找比当前元素更小的元素，并记录其索引。我们将找到的最小元素与当前位置的元素交换，这样每次循环结束后，未排序部分的最前端都会有一个已排序的元素。 虽然选择排序的时间复杂度较高，但在某些特定情况下，例如当数据已经部分有序时，它的表现可能优于其他O(n^2)的算法，如冒泡排序。 在C++ STL中，没有直接提供选择排序的函数。然而，你可以使用`std::sort`函数，它是基于快速排序和插入排序的混合算法，时间复杂度通常为O(n log n)，但在最坏情况下也是O(n^2)。不过，对于大部分实际应用，`std::sort`更为高效。 ```cpp #include <algorithm> #include <vector> int main() { std::vector<int> arr = {5, 3, 8, 1, 9}; std::sort(arr.begin(), arr.end()); // 此时arr已排序 return 0; } ``` 选择排序是一种基础的排序算法，适合用来理解和学习排序算法的基本原理。在实际编程中，由于其效率较低，通常会优先考虑使用效率更高的排序算法，如快速排序、归并排序或STL提供的`std::sort`。