C++ nth_element(STL nth_element)排序算法详解
nth_element() 算法和 partial_sort() 不同。应用的范围由它的第一个和第三个参数指定。第二个参数是一个指向第 n 个元素的迭代器。如果这个范围内的元素是完全有序的,nth_dement() 的执行会导致第 n 个元素被放置在适当的位置。这个范围内,在第 n 个元素之前的元素都小于第 n 个元素,而且它后面的每个元素都会比它大。算法默认用
下面是一个使用 nth_elemen() 的示例:
图 1 nth_element() 算法的操作
第 n 个元素之前的元素都小于它,但不必是有序的。同样,第 n 个元素后的元素都大于它,但也不必是有序的。如果第二个参数和第三个参数相同(元素段的末尾),这时这个算法是无效的。
正如本章前面的算法一样,可以自己定义比较函数作为函数的第 4 个参数:
<
运算符来生成这个结果。下面是一个使用 nth_elemen() 的示例:
std::vector<int> numbers {22, 7, 93, 45, 19, 56, 88, 12, 8, 7, 15, 10}; size_t count {5}; // Index of nth element std::nth_element(std::begin(numbers), std::begin(numbers) + count, std::end(numbers));这里的第 n 个元素是 numbers 容器的第 16 个元素,对应于 numbers[5],图 1 展示了它的工作方式。
图 1 nth_element() 算法的操作
第 n 个元素之前的元素都小于它,但不必是有序的。同样,第 n 个元素后的元素都大于它,但也不必是有序的。如果第二个参数和第三个参数相同(元素段的末尾),这时这个算法是无效的。
正如本章前面的算法一样,可以自己定义比较函数作为函数的第 4 个参数:
std::nth_element(std::begin(numbers), std::begin(numbers) + count, std::end(numbers) , std::greater<>());这里使用
>
运算符来比较函数,所以第 n 个元素将是元素按降序排列后的第 n 个元素。第 n 个元素之前的元素都大于它,之后的元素都小于它。如果 number 容器中的初始值和之前的一样,那么结果为:45 56 93 88 22 19 10 12 15 7 8 7
在你的系统上,第 n 个元素两边元素的顺序可能会不同,但它左边的元素都应该比它大,而右边的元素都应该比它小。所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频