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

有了之前插入排序的基础，实现快速排序不是一件难事，快排的算法用 Haskell 描述就像是下面这样的：

QuickSort [] = []
QuickSort (x:xs) = QuickSort [a | a <- xs, a < x] ++ [x] ++ QuickSort [a | a <- xs, a >= x]

可以看出来，我们还需要补充的列表操作是 Concat，把两个表连接起来，还有 Filter，过滤一个表的元素，实现思路很简单：

template <class ListA, class ListB, class... Tail>
struct ConcatT {};

template <class T, T... ValuesA, T... ValuesB, class... Tail>
struct ConcatT<ValueList<T, ValuesA...>, ValueList<T, ValuesB...>, Tail...>
    : ConcatT<ValueList<T, ValuesA..., ValuesB...>, Tail...> {};

template <class T, T... ValuesA, T... ValuesB>
struct ConcatT<ValueList<T, ValuesA...>, ValueList<T, ValuesB...>> {
    using Type = ValueList<T, ValuesA..., ValuesB...>;
};

template <class ListA, class ListB, class... Tail>
using Concat = typename ConcatT<ListA, ListB, Tail...>::Type;

template <class List, template <class T> class PredicateT,
          bool = IsEmpty<List>::value>
struct FilterT {};

template <class List, template <class T> class PredicateT,
          bool = IsEmpty<List>::value>
using Filter = typename FilterT<List, PredicateT>::Type;

template <class List, template <class T> class PredicateT>
struct FilterT<List, PredicateT, false> {
    using NewTail = Filter<PopFront<List>, PredicateT>;
    using NewHead = Front<List>;
    using Type = IfThenElse<PredicateT<NewHead>::value,
                            PushFront<NewTail, NewHead>, NewTail>;
};

template <class List, template <class T> class PredicateT>
struct FilterT<List, PredicateT, true> {
    using Type = List;
};

然后根据 Haskell 代码写出排序算法：

template <class List, template <class T> class PredicateT,
          bool = IsEmpty<List>::value>
struct PartitionT {};

template <class List, template <class T> class PredicateT>
struct PartitionT<List, PredicateT, false> {
    template <class T>
    struct NegationT {
        constexpr static bool value = !PredicateT<T>::value;
    };
    using Left = Filter<List, PredicateT>;
    using Right = Filter<List, NegationT>;
};

template <class List, template <class T> class PredicateT>
struct PartitionT<List, PredicateT, true> {
    using Left = List;
    using Right = List;
};

template <class List, template <class T, class U> class Compare, bool = IsEmpty<List>::value>
struct QuickSortT {};

template <class List, template <class T, class U> class Compare, bool = IsEmpty<List>::value>
using QuickSort = typename QuickSortT<List, Compare>::Type;

template <class List, template <class T, class U> class Compare>
struct QuickSortT<List, Compare, false> {
    using Pilot = Front<List>;
    template <class T>
    using PredicateT = Compare<T, Front<List>>;
    using Partitioned = PartitionT<PopFront<List>, PredicateT>;
    using SortedLeft = QuickSort<typename Partitioned::Left, Compare>;
    using SortedRight = QuickSort<typename Partitioned::Right, Compare>;
    using Type = Concat<SortedLeft, ValueList<typename Pilot::Type, Pilot::value>, SortedRight>;
};

template <class List, template <class T, class U> class Compare>
struct QuickSortT<List, Compare, true> {
    using Type = List;
};

用插入排序的主函数测试一下：

int main() {
    using TestList = ValueList<int, 17, 1, 15, 9, 8, 19, 16, 10, 11, 7, 4, 14,
                               18, 13, 3, 12, 2, 5, 6, 20>;
    using SortedList = QuickSort<TestList, LessThanT>;
    using ReverseSortedList = QuickSort<TestList, GreaterThanT>;
    std::cout << "Before sorted" << std::endl;
    OutputValueList(TestList());
    std::cout << "After sorted (from small to great)" << std::endl;
    OutputValueList(SortedList());
    std::cout << "After sorted (from great to small)" << std::endl;
    OutputValueList(ReverseSortedList());
    return 0;
}

程序的输出：

Before sorted
17 1 15 9 8 19 16 10 11 7 4 14 18 13 3 12 2 5 6 20
After sorted (from small to great)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
After sorted (from great to small)
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

完整代码片段：https://gist.github.com/howardlau1999/cacaf41c83511cfd591a40aa2527ec3e