这个算法和冒泡法相似，我个人感觉。
- insert_sort.hpp
#ifndef INSERT_SORT_HPP
#define INSERT_SORT_HPP
#include <utility>
//这个算法的时间复杂度是O(n^2)
namespace base {
struct insert_sort {
template <typename C_> void operator()(C_& container) {
auto b = std::begin(container);
auto e = std::end(container);
if (b == e)
return;
for (auto a = b + 1; a != e; ++a) {
auto c = a;
while (((*c) < *(c - 1)) && (c != b)) {
std::swap(*c, *(c - 1));
--c;
}
}
}
};
}
#endif // INSERT_SORT_HPP
测试：
- main.cpp
#include <iostream>
#include <vector>
#include "insert_sort.hpp"
#include "basic_alg.h"
#include "executer.hpp"
using namespace std;
int main()
{
std::vector<int> v{1,9,7,4,3,5,8,6,2};
base::print_msg("Before sort: ", v);
base::executor<base::insert_sort>::exe(v);
base::print_msg("After sort: ", v);
return 0;
}
运行结果：
运行结果
