插入排序C++实现

这个算法和冒泡法相似，我个人感觉。

• 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;
}

运行结果：

运行结果