在 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;
