首页 / 算法 / C++模板元编程----快速排序

C++模板元编程----快速排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++模板元编程----快速排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3644字，纯文字阅读大概需要6分钟。

内容图文

目录

简介

上一篇使用C++模板模板实现了一个选择排序。这一次，更进一步的，实现了一个快速排序算法。关于快速排序的可以看这一篇文章快速排序

实现

和上一次一样，我把快速排序算法分为几个小的步骤，分别实现，然后联合在一起，实现算法。

数据结构定义

和之前类似，不过多定义了一个head_type，同时对一些类型进行了改名。

// 数据结构定义
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;
};

总结

源代码：https://gist.github.com/ink19/2dd0c466db4a11611a9b75e78dd25b4e

和之前的感觉类似，不过使用更加顺手了。

博客原文：博客原文：https://www.cnblogs.com/ink19/p/cpp_template_quick_sort.html

内容总结

以上是互联网集市为您收集整理的C++模板元编程----快速排序全部内容，希望文章能够帮你解决C++模板元编程----快速排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/615664.html

来源：【匿名】