排序算法

MSTL排序算法的实现 更多...

函数
template<typename Iterator, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator >, int > = 0>
bool	is_sorted (Iterator first, Iterator last, Compare comp)
	检查范围是否已排序
template<typename Iterator>
bool	is_sorted (Iterator first, Iterator last)
	检查范围是否已排序
template<typename Iterator, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator >, int > = 0>
Iterator	is_sorted_until (Iterator first, Iterator last, Compare comp)
	查找首个破坏排序的元素
template<typename Iterator>
Iterator	is_sorted_until (Iterator first, Iterator last)
	查找首个破坏排序的元素
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
void	merge_sort (Iterator first, Iterator last, Compare comp)
	归并排序
template<typename Iterator>
void	merge_sort (Iterator first, Iterator last)
	归并排序
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
void	partial_sort (Iterator first, Iterator middle, Iterator last, Compare comp)
	部分排序
template<typename Iterator>
void	partial_sort (Iterator first, Iterator middle, Iterator last)
	部分排序
template<typename Iterator1, typename Iterator2, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator1 > &&is_ranges_rnd_iter_v< Iterator2 >, int > = 0>
Iterator2	partial_sort_copy (Iterator1 first, Iterator1 last, Iterator2 result_first, Iterator2 result_last, Compare comp)
	部分排序并复制到另一个范围
template<typename Iterator1, typename Iterator2>
Iterator2	partial_sort_copy (Iterator1 first, Iterator1 last, Iterator2 result_first, Iterator2 result_last)
	部分排序并复制
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
void	insertion_sort (Iterator first, Iterator last, Compare comp)
	插入排序
template<typename Iterator>
void	insertion_sort (Iterator first, Iterator last)
	插入排序
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
void	introspective_sort (Iterator first, Iterator last, int depth_limit, Compare comp)
	内省排序
template<typename Iterator>
void	introspective_sort (Iterator first, Iterator last, int depth_limit)
	内省排序
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
void	quick_sort (Iterator first, Iterator last, Compare comp)
	快速排序
template<typename Iterator>
void	quick_sort (Iterator first, Iterator last)
	快速排序
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
void	sort (Iterator first, Iterator last, Compare comp)
	标准排序
template<typename Iterator>
void	sort (Iterator first, Iterator last)
	标准排序
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
void	nth_element (Iterator first, Iterator nth, Iterator last, Compare comp)
	第n个元素选择
template<typename Iterator>
void	nth_element (Iterator first, Iterator nth, Iterator last)
	第n个元素选择

详细描述

MSTL排序算法的实现

函数说明

insertion_sort() [1/2]

template<typename Iterator>

void insertion_sort	(	Iterator	first,
		Iterator	last )

插入排序

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始
last	范围结束

在文件 sort.hpp 第 282 行定义.

引用了 _MSTL , 以及 insertion_sort().

insertion_sort() [2/2]

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

void insertion_sort	(	Iterator	first,
		Iterator	last,
		Compare	comp )

插入排序

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	范围起始
last	范围结束
comp	比较函数对象

简单的稳定排序算法，适用于小规模或基本有序的数据。

将每个元素插入到前面已排序子序列的正确位置。

在文件 sort.hpp 第 262 行定义.

引用了 _INNER, _MSTL , 以及 copy_backward().

被这些函数引用 insertion_sort(), nth_element() , 以及 sort().

introspective_sort() [1/2]

template<typename Iterator>

void introspective_sort	(	Iterator	first,
		Iterator	last,
		int	depth_limit )

内省排序

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始
last	范围结束
depth_limit	递归深度限制

在文件 sort.hpp 第 324 行定义.

引用了 _MSTL , 以及 introspective_sort().

introspective_sort() [2/2]

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

void introspective_sort	(	Iterator	first,
		Iterator	last,
		int	depth_limit,
		Compare	comp )

内省排序

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	范围起始
last	范围结束
depth_limit	递归深度限制
comp	比较函数对象

结合了快速排序、堆排序和插入排序的混合排序算法：

1. 使用快速排序递归分区
2. 当递归深度过大时切换到堆排序，避免快速排序的最坏情况
3. 对小规模子序列使用插入排序

在文件 sort.hpp 第 302 行定义.

引用了 _MSTL, introspective_sort(), lomuto_partition(), median() , 以及 partial_sort().

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

is_sorted() [1/2]

template<typename Iterator>

bool is_sorted	(	Iterator	first,
		Iterator	last )

检查范围是否已排序

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

如果范围已排序则返回true，否则返回false

在文件 sort.hpp 第 55 行定义.

引用了 _MSTL , 以及 is_sorted().

is_sorted() [2/2]

template<typename Iterator, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator >, int > = 0>

bool is_sorted	(	Iterator	first,
		Iterator	last,
		Compare	comp )

检查范围是否已排序

模板参数

Iterator	迭代器类型
Compare	比较函数类型

参数

first	范围起始
last	范围结束
comp	比较函数对象

返回

如果范围已按comp排序则返回true，否则返回false

检查范围 [first, last) 是否按照比较函数 comp 排序。

在文件 sort.hpp 第 36 行定义.

引用了 _MSTL , 以及 next().

被这些函数引用 is_sorted().

is_sorted_until() [1/2]

template<typename Iterator>

Iterator is_sorted_until	(	Iterator	first,
		Iterator	last )

查找首个破坏排序的元素

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

指向首个破坏排序的元素的迭代器

在文件 sort.hpp 第 89 行定义.

引用了 _MSTL , 以及 is_sorted_until().

is_sorted_until() [2/2]

template<typename Iterator, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator >, int > = 0>

Iterator is_sorted_until	(	Iterator	first,
		Iterator	last,
		Compare	comp )

查找首个破坏排序的元素

模板参数

Iterator	迭代器类型
Compare	比较函数类型

参数

first	范围起始
last	范围结束
comp	比较函数对象

返回

指向首个破坏排序的元素的迭代器，如果整个范围已排序则返回last

在范围 [first, last) 中查找第一个使得序列不满足排序条件的位置。

在文件 sort.hpp 第 71 行定义.

引用了 _MSTL , 以及 next().

被这些函数引用 is_sorted_until().

merge_sort() [1/2]

template<typename Iterator>

void merge_sort	(	Iterator	first,
		Iterator	last )

归并排序

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始
last	范围结束

在文件 sort.hpp 第 125 行定义.

引用了 _MSTL , 以及 merge_sort().

merge_sort() [2/2]

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

void merge_sort	(	Iterator	first,
		Iterator	last,
		Compare	comp )

归并排序

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	范围起始
last	范围结束
comp	比较函数对象

使用分治策略的稳定排序算法：

1. 递归地将序列分成两半
2. 分别对两半进行排序
3. 合并两个已排序的子序列

在文件 sort.hpp 第 109 行定义.

引用了 _MSTL, distance(), inplace_merge() , 以及 merge_sort().

被这些函数引用 merge_sort() , 以及 merge_sort().

nth_element() [1/2]

template<typename Iterator>

void nth_element	(	Iterator	first,
		Iterator	nth,
		Iterator	last )

第n个元素选择

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始
nth	目标位置
last	范围结束

在文件 sort.hpp 第 484 行定义.

引用了 _MSTL , 以及 nth_element().

nth_element() [2/2]

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

void nth_element	(	Iterator	first,
		Iterator	nth,
		Iterator	last,
		Compare	comp )

第n个元素选择

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	范围起始
nth	目标位置（0-based）
last	范围结束
comp	比较函数对象

重新排列范围 [first, last)，使得位置 nth 的元素是排序后的正确元素， 并且 nth 之前的元素都不大于它，之后的元素都不小于它。 使用快速选择算法实现。

在文件 sort.hpp 第 466 行定义.

引用了 _MSTL, insertion_sort(), lomuto_partition() , 以及 median().

被这些函数引用 nth_element().

partial_sort() [1/2]

template<typename Iterator>

void partial_sort	(	Iterator	first,
		Iterator	middle,
		Iterator	last )

部分排序

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始
middle	部分排序的边界
last	范围结束

在文件 sort.hpp 第 163 行定义.

引用了 _MSTL , 以及 partial_sort().

partial_sort() [2/2]

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

void partial_sort	(	Iterator	first,
		Iterator	middle,
		Iterator	last,
		Compare	comp )

部分排序

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	范围起始
middle	部分排序的边界
last	范围结束
comp	比较函数对象

对范围 [first, last) 进行部分排序，使得 [first, middle) 包含整个范围中最小的元素， 并且这个子范围是已排序的。使用堆排序算法实现。 适用只需要前k个最小（或最大）元素的情况。

在文件 sort.hpp 第 144 行定义.

引用了 _INNER, _MSTL, make_heap() , 以及 sort_heap().

被这些函数引用 introspective_sort() , 以及 partial_sort().

partial_sort_copy() [1/2]

template<typename Iterator1, typename Iterator2>

Iterator2 partial_sort_copy	(	Iterator1	first,
		Iterator1	last,
		Iterator2	result_first,
		Iterator2	result_last )

部分排序并复制

模板参数

Iterator1	输入迭代器类型
Iterator2	随机访问迭代器类型

参数

first	输入范围起始
last	输入范围结束
result_first	输出范围起始
result_last	输出范围结束

返回

输出范围的实际结束位置

在文件 sort.hpp 第 215 行定义.

引用了 _MSTL , 以及 partial_sort_copy().

partial_sort_copy() [2/2]

template<typename Iterator1, typename Iterator2, typename Compare, enable_if_t< is_ranges_input_iter_v< Iterator1 > &&is_ranges_rnd_iter_v< Iterator2 >, int > = 0>

Iterator2 partial_sort_copy	(	Iterator1	first,
		Iterator1	last,
		Iterator2	result_first,
		Iterator2	result_last,
		Compare	comp )

部分排序并复制到另一个范围

模板参数

Iterator1	输入迭代器类型
Iterator2	随机访问迭代器类型
Compare	比较函数类型

参数

first	输入范围起始
last	输入范围结束
result_first	输出范围起始
result_last	输出范围结束
comp	比较函数对象

返回

输出范围的实际结束位置

从输入范围中选取最小的元素，部分排序后复制到输出范围。

在文件 sort.hpp 第 183 行定义.

引用了 _MSTL, adjust_heap(), make_heap() , 以及 sort_heap().

被这些函数引用 partial_sort_copy().

quick_sort() [1/2]

template<typename Iterator>

void quick_sort	(	Iterator	first,
		Iterator	last )

快速排序

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始
last	范围结束

在文件 sort.hpp 第 362 行定义.

引用了 _MSTL , 以及 quick_sort().

quick_sort() [2/2]

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

void quick_sort	(	Iterator	first,
		Iterator	last,
		Compare	comp )

快速排序

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	范围起始
last	范围结束
comp	比较函数对象

经典的分治排序算法：

1. 选择基准值，这里选择最后一个元素
2. 分区：将小于基准值的放在左边，大于等于的放在右边
3. 递归排序左右两部分

注解

此实现容易在已排序数据上出现最坏情况。

在文件 sort.hpp 第 345 行定义.

引用了 _MSTL, iter_swap(), lomuto_partition() , 以及 quick_sort().

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

sort() [1/2]

template<typename Iterator>

void sort	(	Iterator	first,
		Iterator	last )

标准排序

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始
last	范围结束

在文件 sort.hpp 第 447 行定义.

引用了 _MSTL , 以及 sort().

sort() [2/2]

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

void sort	(	Iterator	first,
		Iterator	last,
		Compare	comp )

标准排序

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型

参数

first	范围起始
last	范围结束
comp	比较函数对象

MSTL的标准排序算法，基于内省排序实现：

1. 对大规模数据使用内省排序（快速排序+堆排序）
2. 对阈值内的小规模数据使用插入排序
3. 对大规模数据中的小尾部使用优化的插入排序

在文件 sort.hpp 第 426 行定义.

引用了 _INNER, _MSTL , 以及 insertion_sort().

被这些函数引用 sort().