在 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
