排序算法

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

排序算法 的协作图:

函数
template<typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void	bubble_sort (Iterator first, Iterator last, Compare comp)
	冒泡排序
template<typename Iterator>
NEFORCE_CONSTEXPR20 void	bubble_sort (Iterator first, Iterator last)
	冒泡排序（默认升序）
template<typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void	cocktail_sort (Iterator first, Iterator last, Compare comp)
	鸡尾酒排序（双向冒泡排序）
template<typename Iterator>
NEFORCE_CONSTEXPR20 void	cocktail_sort (Iterator first, Iterator last)
	鸡尾酒排序（默认升序）
template<typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void	select_sort (Iterator first, Iterator last, Compare comp)
	选择排序
template<typename Iterator>
NEFORCE_CONSTEXPR20 void	select_sort (Iterator first, Iterator last)
	选择排序（默认升序）
template<typename Iterator, typename Compare, enable_if_t< is_ranges_rnd_iter_v< Iterator >, int > = 0>
NEFORCE_CONSTEXPR20 void	shell_sort (Iterator first, Iterator last, Compare comp)
	希尔排序
template<typename Iterator>
NEFORCE_CONSTEXPR20 void	shell_sort (Iterator first, Iterator last)
	希尔排序（默认升序）
template<typename Iterator, typename Compare, typename IndexMapper>
NEFORCE_CONSTEXPR20 void	counting_sort (Iterator first, Iterator last, Compare comp, IndexMapper mapper)
	计数排序
template<typename Iterator>
NEFORCE_CONSTEXPR20 void	counting_sort (Iterator first, Iterator last)
	计数排序（默认升序）
template<typename Iterator>
NEFORCE_CONSTEXPR20 void	bucket_sort_less (Iterator first, Iterator last)
	桶排序（升序）
template<typename Iterator>
NEFORCE_CONSTEXPR20 void	bucket_sort_greater (Iterator first, Iterator last)
	桶排序（降序）
template<typename Iterator>
NEFORCE_CONSTEXPR20 void	bucket_sort (Iterator first, Iterator last)
	桶排序（默认升序）
template<typename Iterator, typename Mapper>
NEFORCE_CONSTEXPR20 void	radix_sort_less (Iterator first, Iterator last, Mapper mapper)
	基数排序（升序）
template<typename Iterator, typename Mapper>
NEFORCE_CONSTEXPR20 void	radix_sort_greater (Iterator first, Iterator last, Mapper mapper)
	基数排序（降序）
template<typename Iterator, typename Mapper = _NEFORCE identity<iter_value_t<Iterator>>>
NEFORCE_CONSTEXPR20 void	radix_sort (Iterator first, Iterator last, Mapper mapper=Mapper())
	基数排序（默认升序）
template<typename Iterator>
NEFORCE_CONSTEXPR20 void	smooth_sort (Iterator first, Iterator last)
	平滑排序
template<typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void	tim_sort (Iterator first, Iterator last, Compare comp)
	Tim排序
template<typename Iterator>
NEFORCE_CONSTEXPR20 void	tim_sort (Iterator first, Iterator last)
	Tim排序（默认升序）
template<typename Iterator, typename Compare>
void	monkey_sort (Iterator first, Iterator last, Compare comp)
	猴子排序
template<typename Iterator>
void	monkey_sort (Iterator first, Iterator last)
	猴子排序（默认升序）
template<typename Iterator, typename Compare>
bool	is_sorted (Iterator first, Iterator last, Compare comp)
	检查范围是否已排序
template<typename Iterator>
bool	is_sorted (Iterator first, Iterator last)
	检查范围是否已排序
template<typename Iterator, typename Compare>
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>
void	merge_sort (Iterator first, Iterator last, Compare comp)
	归并排序
template<typename Iterator>
void	merge_sort (Iterator first, Iterator last)
	归并排序
template<typename Iterator, typename Compare>
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>
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>
void	insertion_sort (Iterator first, Iterator last, Compare comp)
	插入排序
template<typename Iterator>
void	insertion_sort (Iterator first, Iterator last)
	插入排序
template<typename Iterator, typename Compare>
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>
void	quick_sort (Iterator first, Iterator last, Compare comp)
	快速排序
template<typename Iterator>
void	quick_sort (Iterator first, Iterator last)
	快速排序
template<typename Iterator, typename Compare>
void	sort (Iterator first, Iterator last, Compare comp)
	标准排序
template<typename Iterator>
void	sort (Iterator first, Iterator last)
	标准排序
template<typename Iterator, typename Compare>
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个元素选择

详细描述

排序算法的实现

本模块提供了多种排序算法的完整实现，涵盖基础排序、高级排序、线性时间排序以及 具有特殊用途或教学价值的排序算法。

遵循的国际标准

本模块中的算法实现参考以下学术文献：

经典排序算法学术文献：

• **C.A.R. Hoare (1961)**：Algorithm 64 — Quicksort Communications of the ACM, 4(7): 321
• **Donald E. Knuth (1998)**：The Art of Computer Programming, Volume 3 — Sorting and Searching ISBN: 978-0201896855
• **Robert Sedgewick (1978)**：Implementing Quicksort programs Communications of the ACM, 21(10): 847-857

现代混合排序算法文献：

• **David R. Musser (1997)**：Introspective Sorting and Selection Algorithms Software: Practice and Experience, 27(8): 983-993 https://doi.org/10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-%23
• **Tim Peters (2002)**：Timsort — Python list sort https://svn.python.org/projects/python/trunk/Objects/listsort.txt

平滑排序学术文献：

• **Edsger W. Dijkstra (1981)**：Smoothsort, an alternative for sorting in situ EWD796a, Burroughs Corporation https://www.cs.utexas.edu/~EWD/transcriptions/EWD07xx/EWD796a.html

算法分类

类别	算法	时间复杂度（平均）	空间复杂度	稳定性
基础排序	bubble_sort, cocktail_sort, select_sort	O(N²)	O(1)	部分稳定
插入排序	insertion_sort, shell_sort	O(N²) / O(N log N)	O(1)	稳定/不稳定
分治排序	merge_sort, quick_sort	O(N log N)	O(N) / O(log N)	稳定/不稳定
混合排序	introspective_sort, tim_sort, smooth_sort	O(N log N)	O(log N) / O(N)	不稳定/稳定
线性时间排序	counting_sort, bucket_sort, radix_sort	O(N) / O(N+k)	O(k) / O(N+k)	稳定
部分排序	partial_sort, nth_element	O(N log k) / O(N)	O(1)	不稳定
娱乐/教学排序	monkey_sort	O((N+1)!)	O(1)	不稳定

混合排序算法详解

**内省排序（Introspective Sort）**：

• 结合快速排序、堆排序和插入排序
• 默认递归深度限制：2 × ⌊log₂(N)⌋
• 超过深度限制时切换到堆排序，避免 O(N²) 最坏情况
• 小规模子序列（≤阈值）使用插入排序

**TimSort**：

• 结合归并排序和插入排序
• 识别并利用数据中的自然有序片段（run）
• 最小归并片段大小（minrun）：32
• Python 和 Java 默认排序算法

**平滑排序（Smoothsort）**：

• 基于莱昂纳多堆（Leonardo Heap）
• 在接近有序的序列上达到 O(N) 时间复杂度
• 由 Edsger W. Dijkstra 设计

线性时间排序算法

**计数排序（Counting Sort）**：

• 适用于整数或可映射为整数的类型
• 时间复杂度：O(N + k)，k 为元素范围
• 要求元素范围不宜过大

**桶排序（Bucket Sort）**：

• 适用于均匀分布的整数或浮点数
• 将元素分配到多个桶中，每个桶内部排序

**基数排序（Radix Sort）**：

• 从最低有效位（LSD）或最高有效位（MSD）开始排序
• 时间复杂度：O(d × (N + k))，d 为位数
• 适合定长整数或字符串

部分排序

**partial_sort**：

• 找出前 k 个最小（或最大）元素并排序
• 使用堆排序实现，时间复杂度 O(N log k)
• 适用于"Top K"问题

**nth_element**：

• 找出第 n 个顺序统计量
• 使用快速选择算法，平均时间复杂度 O(N)
• nth 之前元素 ≤ nth ≤ nth 之后元素

稳定性说明

算法	稳定性	说明
bubble_sort	稳定	相邻元素相等时不交换
cocktail_sort	稳定	双向冒泡，保持相等元素相对顺序
select_sort	不稳定	交换可能破坏相等元素的相对顺序
insertion_sort	稳定	相等元素不移动
merge_sort	稳定	合并时优先取左侧元素
quick_sort	不稳定	分区交换破坏相对顺序
shell_sort	不稳定	间隔插入排序破坏顺序
heap_sort	不稳定	堆操作不保持相对顺序
introspective_sort	不稳定	结合快速排序和堆排序，均不稳定
tim_sort	稳定	插入排序和归并排序均稳定
smooth_sort	不稳定	基于堆结构，不保持相对顺序
counting_sort	稳定	反向遍历保持稳定性
bucket_sort	稳定	桶内保持插入顺序
radix_sort	稳定	每轮计数排序保持稳定性

实现细节

特性	规范参数
迭代器要求	各算法要求不同，见各函数文档
比较器要求	严格弱序（Strict Weak Ordering）
小序列优化	默认阈值 MEMORY_ALIGN_THRESHHOLD
递归深度限制	2 × ⌊log₂(N)⌋（内省排序）

注解

对于大多数应用场景，推荐使用标准排序 sort（内省排序）， 它在平均和最坏情况下均表现良好，且经过了充分测试。

参见

https://en.cppreference.com/w/cpp/algorithm/sort

https://en.wikipedia.org/wiki/Sorting_algorithm

https://www.cs.utexas.edu/~EWD/transcriptions/EWD07xx/EWD796a.html

函数说明

bubble_sort() [1/2]

template<typename Iterator>

NEFORCE_CONSTEXPR20 void bubble_sort	(	Iterator	first,
		Iterator	last )

冒泡排序（默认升序）

模板参数

Iterator

双向迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

在文件 ext_sort.hpp 第 76 行定义.

引用了 bubble_sort().

bubble_sort() [2/2]

template<typename Iterator, typename Compare>

NEFORCE_CONSTEXPR20 void bubble_sort	(	Iterator	first,
		Iterator	last,
		Compare	comp )

冒泡排序

模板参数

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

参数

first	序列起始迭代器
last	序列结束迭代器
comp	比较函数对象

时间复杂度：平均O(N²)，最优O(N)，最差O(N²) 空间复杂度：O(1) 稳定性：稳定

通过重复交换相邻的逆序元素将最大元素冒泡到末尾。

在文件 ext_sort.hpp 第 42 行定义.

引用了 end(), is_invocable_v, iter_swap(), make_reverse_iterator() , 以及 next().

被这些函数引用 bubble_sort().

bucket_sort()

template<typename Iterator>

NEFORCE_CONSTEXPR20 void bucket_sort	(	Iterator	first,
		Iterator	last )

桶排序（默认升序）

模板参数

Iterator

前向迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

在文件 ext_sort.hpp 第 378 行定义.

引用了 bucket_sort_less().

bucket_sort_greater()

template<typename Iterator>

NEFORCE_CONSTEXPR20 void bucket_sort_greater	(	Iterator	first,
		Iterator	last )

桶排序（降序）

模板参数

Iterator

前向迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

在文件 ext_sort.hpp 第 347 行定义.

引用了 pair< T1, T2 >::first, is_ranges_fwd_iter_v, minmax_element(), pair< T1, T2 >::second , 以及 vector< T, Alloc >::size().

bucket_sort_less()

template<typename Iterator>

NEFORCE_CONSTEXPR20 void bucket_sort_less	(	Iterator	first,
		Iterator	last )

桶排序（升序）

模板参数

Iterator

前向迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

时间复杂度：平均O(N + k)，最差O(N²) 空间复杂度：O(N + k) 稳定性：稳定

适用于均匀分布的整数或浮点数。

在文件 ext_sort.hpp 第 316 行定义.

引用了 pair< T1, T2 >::first, is_ranges_fwd_iter_v, minmax_element(), pair< T1, T2 >::second , 以及 vector< T, Alloc >::size().

被这些函数引用 bucket_sort().

cocktail_sort() [1/2]

template<typename Iterator>

NEFORCE_CONSTEXPR20 void cocktail_sort	(	Iterator	first,
		Iterator	last )

鸡尾酒排序（默认升序）

模板参数

Iterator

双向迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

在文件 ext_sort.hpp 第 140 行定义.

引用了 cocktail_sort().

cocktail_sort() [2/2]

template<typename Iterator, typename Compare>

NEFORCE_CONSTEXPR20 void cocktail_sort	(	Iterator	first,
		Iterator	last,
		Compare	comp )

鸡尾酒排序（双向冒泡排序）

模板参数

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

参数

first	序列起始迭代器
last	序列结束迭代器
comp	比较函数对象

时间复杂度：平均O(N²)，最优O(N)，最差O(N²) 空间复杂度：O(1) 稳定性：稳定

冒泡排序的改进版本，同时从两端进行冒泡，减少循环次数。

在文件 ext_sort.hpp 第 95 行定义.

引用了 is_invocable_v, is_ranges_bid_iter_v, iter_swap(), next() , 以及 prev().

被这些函数引用 cocktail_sort().

counting_sort() [1/2]

template<typename Iterator>

NEFORCE_CONSTEXPR20 void counting_sort	(	Iterator	first,
		Iterator	last )

计数排序（默认升序）

模板参数

Iterator

随机访问迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

在文件 ext_sort.hpp 第 298 行定义.

引用了 counting_sort().

counting_sort() [2/2]

template<typename Iterator, typename Compare, typename IndexMapper>

NEFORCE_CONSTEXPR20 void counting_sort	(	Iterator	first,
		Iterator	last,
		Compare	comp,
		IndexMapper	mapper )

计数排序

模板参数

Iterator	随机访问迭代器类型
Compare	比较函数类型
IndexMapper	索引映射函数类型

参数

first	序列起始迭代器
last	序列结束迭代器
comp	比较函数对象
mapper	将元素映射为整数索引的函数

时间复杂度：O(N + k)，其中k是元素范围 空间复杂度：O(k) 稳定性：稳定

适用于整数或可映射为整数的类型，范围不宜过大。

在文件 ext_sort.hpp 第 253 行定义.

引用了 vector< T, Alloc >::begin(), copy(), count(), distance(), vector< T, Alloc >::end(), is_invocable_v, is_ranges_rnd_iter_v, make_reverse_iterator() , 以及 minmax_element().

被这些函数引用 counting_sort().

insertion_sort() [1/2]

template<typename Iterator>

void insertion_sort	(	Iterator	first,
		Iterator	last )

插入排序

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始
last	范围结束

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

引用了 insertion_sort().

insertion_sort() [2/2]

template<typename Iterator, typename Compare>

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

插入排序

模板参数

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

参数

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

简单的稳定排序算法，适用于小规模或基本有序的数据。 将每个元素插入到前面已排序子序列的正确位置。

时间复杂度：最优O(N)，最差O(N²) 空间复杂度：O(1) 稳定性：稳定

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

引用了 copy_backward(), is_invocable_v , 以及 is_ranges_rnd_iter_v.

被这些函数引用 insertion_sort(), nth_element(), sort() , 以及 tim_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 第 481 行定义.

引用了 introspective_sort().

introspective_sort() [2/2]

template<typename Iterator, typename Compare>

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

内省排序

模板参数

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

参数

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

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

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

时间复杂度：O(N log N) 空间复杂度：O(log N) 稳定性：不稳定

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

引用了 introspective_sort(), is_invocable_v, 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 第 180 行定义.

引用了 is_sorted().

is_sorted() [2/2]

template<typename Iterator, typename Compare>

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

检查范围是否已排序

模板参数

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

参数

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

返回

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

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

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

引用了 is_invocable_v, is_ranges_input_iter_v , 以及 next().

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

is_sorted_until() [1/2]

template<typename Iterator>

Iterator is_sorted_until	(	Iterator	first,
		Iterator	last )

查找首个破坏排序的元素

模板参数

Iterator

迭代器类型

参数

first	范围起始
last	范围结束

返回

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

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

引用了 is_sorted_until().

is_sorted_until() [2/2]

template<typename Iterator, typename Compare>

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

查找首个破坏排序的元素

模板参数

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

参数

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

返回

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

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

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

引用了 is_invocable_v, is_ranges_input_iter_v , 以及 next().

被这些函数引用 is_sorted_until().

merge_sort() [1/2]

template<typename Iterator>

void merge_sort	(	Iterator	first,
		Iterator	last )

归并排序

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始
last	范围结束

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

引用了 merge_sort().

merge_sort() [2/2]

template<typename Iterator, typename Compare>

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

归并排序

模板参数

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

参数

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

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

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

时间复杂度：O(N log N) 空间复杂度：O(N) 稳定性：稳定

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

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

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

monkey_sort() [1/2]

template<typename Iterator>

void monkey_sort	(	Iterator	first,
		Iterator	last )

猴子排序（默认升序）

模板参数

Iterator

随机访问迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

警告

仅用于教学和娱乐目的，切勿用于实际生产环境。

在文件 ext_sort.hpp 第 630 行定义.

引用了 monkey_sort().

monkey_sort() [2/2]

template<typename Iterator, typename Compare>

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

猴子排序

模板参数

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

参数

first	序列起始迭代器
last	序列结束迭代器
comp	比较函数对象

时间复杂度：平均O((N+1)!)，理论上无限 空间复杂度：O(1) 稳定性：不稳定

通过随机打乱并检查是否有序来进行排序。

警告

仅用于教学和娱乐目的，切勿用于实际生产环境。

在文件 ext_sort.hpp 第 615 行定义.

引用了 is_sorted() , 以及 shuffle().

被这些函数引用 monkey_sort().

nth_element() [1/2]

template<typename Iterator>

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

第n个元素选择

模板参数

Iterator

随机访问迭代器类型

参数

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

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

引用了 nth_element().

nth_element() [2/2]

template<typename Iterator, typename Compare>

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 第 634 行定义.

引用了 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 第 304 行定义.

引用了 partial_sort().

partial_sort() [2/2]

template<typename Iterator, typename Compare>

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

部分排序

模板参数

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

参数

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

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

时间复杂度：O(N log k)，其中k = middle - first

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

引用了 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 第 360 行定义.

引用了 partial_sort_copy().

partial_sort_copy() [2/2]

template<typename Iterator1, typename Iterator2, typename Compare>

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	比较函数对象

返回

输出范围的实际结束位置

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

时间复杂度：O(N log M)，其中M = result_last - result_first

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

引用了 adjust_heap(), is_ranges_input_iter_v, 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 第 522 行定义.

引用了 quick_sort().

quick_sort() [2/2]

template<typename Iterator, typename Compare>

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

快速排序

模板参数

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

参数

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

经典的分治排序算法：

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

时间复杂度：平均O(N log N)，最差O(N²) 空间复杂度：O(log N)（递归栈） 稳定性：不稳定

注解

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

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

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

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

radix_sort()

template<typename Iterator, typename Mapper = _NEFORCE identity<iter_value_t<Iterator>>>

NEFORCE_CONSTEXPR20 void radix_sort	(	Iterator	first,
		Iterator	last,
		Mapper	mapper = Mapper() )

基数排序（默认升序）

模板参数

Iterator	随机访问迭代器类型
Mapper	映射函数类型

参数

first	序列起始迭代器
last	序列结束迭代器
mapper	将元素映射为整数的函数

在文件 ext_sort.hpp 第 531 行定义.

引用了 radix_sort_less().

radix_sort_greater()

template<typename Iterator, typename Mapper>

NEFORCE_CONSTEXPR20 void radix_sort_greater	(	Iterator	first,
		Iterator	last,
		Mapper	mapper )

基数排序（降序）

模板参数

Iterator	随机访问迭代器类型
Mapper	映射函数类型

参数

first	序列起始迭代器
last	序列结束迭代器
mapper	将元素映射为整数的函数

在文件 ext_sort.hpp 第 477 行定义.

引用了 vector< T, Alloc >::begin(), count(), distance(), vector< T, Alloc >::end(), fill(), is_invocable_v , 以及 is_ranges_rnd_iter_v.

radix_sort_less()

template<typename Iterator, typename Mapper>

NEFORCE_CONSTEXPR20 void radix_sort_less	(	Iterator	first,
		Iterator	last,
		Mapper	mapper )

基数排序（升序）

模板参数

Iterator	随机访问迭代器类型
Mapper	映射函数类型

参数

first	序列起始迭代器
last	序列结束迭代器
mapper	将元素映射为整数的函数

时间复杂度：O(d * (N + k))，d是位数 空间复杂度：O(N + k) 稳定性：稳定

适用于整数或可分解为固定数位的类型。

在文件 ext_sort.hpp 第 423 行定义.

引用了 vector< T, Alloc >::begin(), count(), distance(), vector< T, Alloc >::end(), fill(), is_invocable_v , 以及 is_ranges_rnd_iter_v.

被这些函数引用 radix_sort().

select_sort() [1/2]

template<typename Iterator>

NEFORCE_CONSTEXPR20 void select_sort	(	Iterator	first,
		Iterator	last )

选择排序（默认升序）

模板参数

Iterator

前向迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

在文件 ext_sort.hpp 第 186 行定义.

引用了 select_sort().

select_sort() [2/2]

template<typename Iterator, typename Compare>

NEFORCE_CONSTEXPR20 void select_sort	(	Iterator	first,
		Iterator	last,
		Compare	comp )

选择排序

模板参数

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

参数

first	序列起始迭代器
last	序列结束迭代器
comp	比较函数对象

时间复杂度：O(N²) 空间复杂度：O(1) 稳定性：不稳定

每次从未排序部分选择元素放到已排序部分的末尾。

在文件 ext_sort.hpp 第 159 行定义.

引用了 is_invocable_v, is_ranges_fwd_iter_v, iter_swap() , 以及 min().

被这些函数引用 select_sort().

shell_sort() [1/2]

template<typename Iterator>

NEFORCE_CONSTEXPR20 void shell_sort	(	Iterator	first,
		Iterator	last )

希尔排序（默认升序）

模板参数

Iterator

随机访问迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

在文件 ext_sort.hpp 第 232 行定义.

引用了 shell_sort().

shell_sort() [2/2]

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

NEFORCE_CONSTEXPR20 void shell_sort	(	Iterator	first,
		Iterator	last,
		Compare	comp )

希尔排序

模板参数

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

参数

first	序列起始迭代器
last	序列结束迭代器
comp	比较函数对象

时间复杂度：平均O(N log N)，最差O(N²) 空间复杂度：O(1) 稳定性：不稳定

插入排序的改进版本，通过比较相距一定间隔的元素来工作。

在文件 ext_sort.hpp 第 205 行定义.

引用了 distance(), is_invocable_v, is_ranges_rnd_iter_v , 以及 move().

被这些函数引用 shell_sort().

smooth_sort()

template<typename Iterator>

NEFORCE_CONSTEXPR20 void smooth_sort	(	Iterator	first,
		Iterator	last )

平滑排序

模板参数

Iterator

随机访问迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

时间复杂度：O(N log N) 空间复杂度：O(1) 稳定性：不稳定

基于莱昂纳多堆的排序算法，是堆排序的改进版本， 在部分有序的序列上表现优异。

在文件 ext_sort.hpp 第 549 行定义.

引用了 make_leonardo_heap() , 以及 sort_leonardo_heap().

sort() [1/2]

template<typename Iterator>

void sort	(	Iterator	first,
		Iterator	last )

标准排序

模板参数

Iterator

随机访问迭代器类型

参数

first	范围起始
last	范围结束

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

引用了 sort().

sort() [2/2]

template<typename Iterator, typename Compare>

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

标准排序

模板参数

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

参数

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

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

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

时间复杂度：O(N log N) 空间复杂度：O(log N) 稳定性：不稳定

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

引用了 insertion_sort().

被这些函数引用 sort().

tim_sort() [1/2]

template<typename Iterator>

NEFORCE_CONSTEXPR20 void tim_sort	(	Iterator	first,
		Iterator	last )

Tim排序（默认升序）

模板参数

Iterator

随机访问迭代器类型

参数

first	序列起始迭代器
last	序列结束迭代器

在文件 ext_sort.hpp 第 594 行定义.

引用了 tim_sort().

tim_sort() [2/2]

template<typename Iterator, typename Compare>

NEFORCE_CONSTEXPR20 void tim_sort	(	Iterator	first,
		Iterator	last,
		Compare	comp )

Tim排序

模板参数

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

参数

first	序列起始迭代器
last	序列结束迭代器
comp	比较函数对象

时间复杂度：O(N log N) 空间复杂度：O(N) 稳定性：稳定

混合排序算法，结合了归并排序和插入排序。

在文件 ext_sort.hpp 第 569 行定义.

引用了 distance(), end(), inplace_merge(), insertion_sort(), min() , 以及 size().

被这些函数引用 tim_sort().