在 C++ 中实现插入排序算法
本文将演示如何在 C++ 中实现插入排序算法。
在 C++ 中为 std::vector 容器实现插入排序
在本指南中，我们将向你展示如何将插入排序实现为一个单独的函数，该函数引用 std::vector 对象并就地修改内容。插入排序遍历向量中的每个元素。它通过按倒序比较当前元素和前一个元素来确保当前位置之前的所有元素都被排序。
一般来说，比较的顺序对算法性能没有太大影响，但我们假设为后向顺序并相应地实现代码。我们还将假设按升序对元素进行排序。尽管如此，在实际情况下，通用排序算法应该能够将自定义比较函数作为参数。请注意，如果当前元素小于前一个元素，则比较操作通常会强制该元素右移。后一个操作是使用另一个嵌套的 for 循环实现的，该循环对顺序错误的元素调用 std::swap 函数。
以下代码片段包含 insertionSort 函数，其中外部 for 循环负责整个数组遍历。我们将迭代器初始化为向量中的第二个元素，因为接下来的步骤包括与前一个元素的比较——内部循环从当前元素向下迭代到第一个元素以比较它们。如果比较函数的计算结果为 true，则交换该对。请注意，当至少一个前一个元素小于当前元素时，else 表达式会强制内部循环中断。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void insertionSort(vector<T> &vec) {
for (auto it = vec.begin() + 1; it != vec.end(); ++it) {
auto key = it;
for (auto i = it - 1; i >= vec.begin(); --i) {
if (*i > *key) {
std::swap(*i, *key);
key--;
} else {
break;
}
}
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
insertionSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
输出：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
或者，我们可以使用 while 循环结构重新实现 insertionSort 函数，如果后者更适合用户阅读。两种算法遵循类似的实现逻辑，都利用 std::swap 函数来移动元素。插入排序在大数据集上是一种非常低效的算法，其平均性能为 O(n2)。
插入排序类似于另一种称为选择排序的二次算法；它们都遍历向量。在 n 次迭代之后，对前 n 个元素进行排序。尽管如此，与插入排序相比，选择排序从当前位置计算向前的元素。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void insertionSort2(vector<T> &vec) {
auto iter = vec.begin() + 1;
while (iter != vec.end()) {
auto key = iter;
auto it = iter - 1;
while (it >= vec.begin() && *it > *key) {
std::swap(*it, *key);
key--;
it--;
}
iter++;
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
insertionSort2(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
输出：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
与其他 O(n2) 算法相比，插入排序在实践中可以更有效，因为它并不总是需要将当前元素与每个前面的元素进行比较。同时，选择排序必须始终搜索未排序子数组中的每个元素以找到最小（或最大）元素。请注意，我们可以在 std::string 的向量上使用 insertionSort 函数实现，因为后者实现了比较运算符重载。下一个示例演示了它与字符串向量的基本用法，并打印了单词的排序列表。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void insertionSort(vector<T> &vec) {
auto iter = vec.begin() + 1;
while (iter != vec.end()) {
auto key = iter;
auto it = iter - 1;
while (it >= vec.begin() && *it > *key) {
std::swap(*it, *key);
key--;
it--;
}
iter++;
}
}
int main() {
vector<string> vec2 = {"highway", "song", "work",
"borland", "death", "woman"};
printVector(vec2);
insertionSort(vec2);
printVector(vec2);
return EXIT_SUCCESS;
}
输出：
highway; song; work; borland; death; woman;
borland; death; highway; song; woman; work;
