Last active
November 19, 2021 02:29
-
-
Save ink19/2dd0c466db4a11611a9b75e78dd25b4e to your computer and use it in GitHub Desktop.
template quick sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <array> | |
// 数据结构定义 | |
template<int ...> | |
struct mvector; | |
template<int ...data, int _head> | |
struct mvector<_head, data...> { | |
constexpr static int head = _head; | |
typedef mvector<_head> head_type; | |
typedef mvector<data...> tail_type; | |
constexpr static std::array<int, 1 + sizeof...(data)> value = {_head, data...}; | |
}; | |
template<int _head> | |
struct mvector<_head> { | |
constexpr static int head = _head; | |
typedef mvector<_head> head_type; | |
typedef mvector<> tail_type; | |
constexpr static std::array<int, 1> value = {_head}; | |
}; | |
template<> | |
struct mvector<> { | |
constexpr static int head = -1; | |
typedef mvector<> head_type; | |
typedef mvector<> tail_type; | |
constexpr static std::array<int, 0> value = {}; | |
}; | |
// 在数组前增加一个元素 | |
template<int data, typename list> | |
struct add_to_list; | |
template<int data, int ...data_list> | |
struct add_to_list<data, mvector<data_list...>> { | |
typedef mvector<data, data_list...> result_type; | |
}; | |
// 判断,输出一个类型 | |
template<bool, typename T, typename S> | |
struct m_type_if; | |
template<typename T, typename S> | |
struct m_type_if<true, T, S> { | |
typedef T result_type; | |
typedef S not_result_type; | |
}; | |
template<typename T, typename S> | |
struct m_type_if<false, T, S> { | |
typedef S result_type; | |
typedef T not_result_type; | |
}; | |
// 分堆 | |
template<typename , typename> | |
struct m_diff; | |
template<typename _mid, int ...data, int data_head> | |
struct m_diff<_mid, mvector<data_head, data...>> { | |
typedef _mid mid; | |
typedef m_diff<_mid, mvector<data...>> next_type; | |
typedef typename m_type_if<data_head < mid::head, typename add_to_list<data_head, typename next_type::right_type>::result_type, typename next_type::right_type>::result_type right_type; | |
typedef typename m_type_if<data_head >= mid::head, typename add_to_list<data_head, typename next_type::left_type>::result_type, typename next_type::left_type>::result_type left_type; | |
}; | |
template<typename _mid> | |
struct m_diff<_mid, mvector<>> { | |
typedef _mid mid; | |
typedef m_diff<_mid, mvector<>> next_type; | |
typedef mvector<> right_type; | |
typedef mvector<> left_type; | |
}; | |
// 合并 | |
template<typename, typename, typename> | |
struct combine_result; | |
template<int ...data_S, int mid, int ...data_T> | |
struct combine_result<mvector<data_S...>, mvector<mid>, mvector<data_T...>> { | |
typedef mvector<data_S..., mid, data_T...> result_type; | |
}; | |
// 快排 | |
template<typename data> | |
struct QuickSortWork; | |
template<int ...data> | |
struct QuickSortWork<mvector<data...>> { | |
typedef m_diff<typename mvector<data...>::head_type, typename mvector<data...>::tail_type> diffed_type; | |
typedef typename QuickSortWork<typename diffed_type::right_type>::result_type right_type; | |
typedef typename QuickSortWork<typename diffed_type::left_type>::result_type left_type; | |
typedef typename combine_result<right_type, typename mvector<data...>::head_type, left_type>::result_type result_type; | |
}; | |
template<> | |
struct QuickSortWork<mvector<>> { | |
typedef mvector<> result_type; | |
}; | |
template<int ...data> | |
struct QuickSort { | |
typedef QuickSortWork<mvector<data...>> work_type; | |
constexpr static std::array<int, sizeof...(data)> result = work_type::result_type::value; | |
}; | |
constexpr static std::array<int, 8> result = QuickSort<1, 123, 4, 31, 12, 4, 56, 8>::result; | |
int main() { | |
for (auto item : result) { | |
std::cout << item << ","; | |
} | |
std::cout << std::endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment