在 C++ 中实现选择排序算法
Jinku Hu
2023年10月12日
本文将讲解如何在 C++ 中实现选择排序算法。
在 C++ 中实现 std::vector 容器的选择排序
在简单的排序算法中，你可以认为选择排序是最容易实现的一种；尽管如此，它的复杂度为 O(n2)，并且在大型向量上效率极低。
选择排序可以指定为以下例程：首先，我们找到向量中的最小值并将其与第一个元素交换。然后，我们将指针移动到第二个元素，并从剩余的子向量中找到最小值与第二个元素交换。我们对向量的其余部分继续前面的步骤，同时将指针一次移动一个元素。
选择排序的另一种解释可能是将输入向量分成两部分 L：第一部分是已排序的子向量，第二部分是未排序元素的剩余子向量（按原始顺序）。由于不能假设已排序子向量存在于给定向量中，因此我们应该选择第一个元素作为已排序子向量和未排序子向量之间的除数。因此，当我们开始用起始位置的元素交换最小值时。向量会自然地分为已排序和未排序的部分。
在下面的示例中，我们实现了 selectionSort 函数，该函数接受对 std::vector 对象的引用并对元素进行就地修改。我们利用 std::min_element 算法在每次迭代中找到最小值；这有助于第一次更好地理解算法。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void selectionSort(vector<T> &vec) {
for (auto it = vec.begin(); it != vec.end(); ++it) {
std::swap(*it, *std::min_element(it, vec.end()));
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
selectionSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
输出：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
或者，我们可以使用第二个 for 循环重写 selectionSort 函数，该循环为每次迭代的剩余未排序子向量找到最小值。此版本适用于算法复杂度分析。尽管选择排序算法的运行时间是二次的，但与 O(nlogn) 算法（如归并排序或堆排序）相比，它在较小的向量上的效率惊人。请注意，我们仍然使用一个 STL 函数 std::swap，在这种情况下它是一个恒定时间操作，并且代码示例简洁有用。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void selectionSort(vector<T> &vec) {
for (auto it = vec.begin(); it != vec.end(); ++it) {
auto min = it;
for (auto i = it + 1; i != vec.end(); ++i) {
if (*i < *min) min = i;
}
std::swap(*it, *min);
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
selectionSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
输出：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
作者： Jinku Hu
