有了之前插入排序的基础，实现快速排序不是一件难事，快排的算法用 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