C++11STL中常用排序算法有哪些,请详细介绍
时间: 2023-12-10 13:04:33 浏览: 49
C++11STL中常用的排序算法有以下几种:
1. sort
sort是STL中最常用的排序算法,它可以对容器中的元素进行排序。sort的时间复杂度为O(NlogN),使用快速排序算法实现。sort的基本使用方法如下:
```c++
sort(begin, end); // 对区间[begin, end)内的元素排序
```
其中,`begin`和`end`分别是容器中要排序的元素的起始和结束迭代器。
此外,sort还可以接受一个可调用对象作为参数,来实现自定义的排序方法。例如,可以按照元素的某个属性进行排序:
```c++
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
return a.property < b.property;
}); // 按照元素的property属性进行排序
```
2. stable_sort
stable_sort与sort的用法类似,也可以对容器中的元素进行排序,但它保证了相等元素的相对顺序不会发生改变。stable_sort的时间复杂度为O(NlogN),使用归并排序算法实现。stable_sort的基本使用方法如下:
```c++
stable_sort(begin, end); // 对区间[begin, end)内的元素排序
```
3. partial_sort
partial_sort可以对容器中的元素进行部分排序,即只将前k个最小(或最大)的元素放在容器的前k个位置上。partial_sort的时间复杂度为O(Nlogk),使用堆排序算法实现。partial_sort的基本使用方法如下:
```c++
partial_sort(begin, middle, end); // 将区间[begin, end)内的前middle-begin个元素排序,其他元素保持原有顺序
```
其中,`middle`是一个迭代器,指向容器中排序后前middle-begin个元素的末尾位置。
4. nth_element
nth_element可以找出容器中第k小(或第k大)的元素。nth_element的时间复杂度为O(N),使用快速选择算法实现。nth_element的基本使用方法如下:
```c++
nth_element(begin, nth, end); // 将区间[begin, end)内的元素排序,使得第nth个元素是第nth小的元素
```
其中,`nth`是一个迭代器,指向容器中第nth小的元素。
以上就是C++11STL中常用的排序算法,可以根据实际需求选择适合的算法。