分区算法

MSTL分区算法的实现 更多...

函数
template<typename Iterator, typename Predicate, enable_if_t< is_ranges_bid_iter_v< Iterator >, int > = 0>
constexpr Iterator	partition (Iterator first, Iterator last, Predicate pred)
	分区算法
template<typename Iterator, typename T, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
constexpr Iterator	lomuto_partition (Iterator first, Iterator last, const T &pivot, Compare comp)
	Lomuto分区算法
template<typename Iterator, typename T>
constexpr Iterator	lomuto_partition (Iterator first, Iterator last, const T &pivot)
	Lomuto分区算法

详细描述

MSTL分区算法的实现

函数说明

lomuto_partition() [1/2]

template<typename Iterator, typename T>

Iterator lomuto_partition ( Iterator first, Iterator last, const T & pivot )

constexpr

Lomuto分区算法

模板参数

Iterator	随机访问迭代器类型
T	基准值类型

参数

first	范围起始
last	范围结束
pivot	基准值

返回

指向第一部分结束位置的迭代器

在文件 partition.hpp 第 105 行定义.

引用了 _MSTL , 以及 lomuto_partition().

lomuto_partition() [2/2]

template<typename Iterator, typename T, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>

Iterator lomuto_partition ( Iterator first, Iterator last, const T & pivot, Compare comp )

constexpr

Lomuto分区算法

模板参数

Iterator	随机访问迭代器类型
T	基准值类型
Compare	比较函数类型

参数

first	范围起始
last	范围结束
pivot	基准值
comp	比较函数对象

返回

指向基准值最终位置的迭代器

Lomuto分区算法，常用于快速排序。 将范围重新排列，使得所有小于基准值的元素出现在基准值之前或等于基准值的元素之前， 所有大于基准值的元素出现在基准值之后。

算法步骤：

1. 从两端向中间扫描
2. 从左找到第一个不小于基准值的元素
3. 从右找到第一个不大于基准值的元素
4. 交换这两个元素
5. 重复直到指针相遇

在文件 partition.hpp 第 83 行定义.

引用了 _MSTL , 以及 iter_swap().

被这些函数引用 introspective_sort(), lomuto_partition(), nth_element() , 以及 quick_sort().

partition()

template<typename Iterator, typename Predicate, enable_if_t< is_ranges_bid_iter_v< Iterator >, int > = 0>

Iterator partition ( Iterator first, Iterator last, Predicate pred )

constexpr

分区算法

模板参数

Iterator	迭代器类型
Predicate	谓词类型

参数

first	范围起始
last	范围结束
pred	一元谓词

返回

指向第二部分第一个元素的迭代器

将范围 [first, last) 重新排列，使得所有满足谓词 pred 的元素都出现在不满足谓词的元素之前。 不保证相同类别的元素保持原始相对顺序。

算法使用双向迭代器，从两端向中间扫描：

1. 从前向后找到第一个不满足谓词的元素
2. 从后向前找到第一个满足谓词的元素
3. 交换这两个元素
4. 重复直到两个扫描指针相遇

在文件 partition.hpp 第 40 行定义.

引用了 _MSTL , 以及 iter_swap().