STL sort排序

STL sort排序算法

C++ STL 标准库提供有很多实用的排序函数，通过调用它们，我们可以很轻松地实现对普通数组或者容器中指定范围内的元素进行排序。

STL排序算法详解

函数	功能
sort(first, last)	对容器或普通数组中 [first, last) 范围内的元素进行排序，默认进行升序排序。
stable_sort(first, last)	和 sort() 函数功能相似，不同之处在于，对于 [first, last) 范围内值相同的元素，该函数不会改变它们的相对位置。
partial_sort(first, middle, last)	从 [first,last) 范围内，筛选出 muddle-first 个最小的元素并排序存放在 [first，middle) 区间中。
partial_sort_copy(first, last, result_first, result_last)	从 [first, last) 范围内筛选出 result_last-result_first 个元素排序并存储到 [result_first, result_last) 指定的范围中。
is_sorted (first, last)	检测 [first, last) 范围内是否已经排好序，默认检测是否按升序排序。
is_sorted_until (first, last)	和 is_sorted() 函数功能类似，唯一的区别在于，如果 [first, last) 范围的元素没有排好序，则该函数会返回一个指向首个不遵循排序规则的元素的迭代器。
void nth_element (first, nth, last)	找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

STL sort函数详解

说明

C++ STL 标准库中的 sort() 函数，本质就是一个模板函数。该函数专门用来对容器或普通数组中指定范围内的元素进行排序，排序规则默认以元素值的大小做升序排序，除此之外我们也可以选择标准库提供的其它排序规则（比如 std::greater<T> 降序排序规则），甚至还可以自定义排序规则。

sort() 函数是基于快速排序实现的，需要注意的是，sort() 函数受到底层实现方式的限制，它仅适用于普通数组和部分类型的容器。换句话说，只有普通数组和具备以下条件的容器，才能使用 sort() 函数：

容器支持的迭代器类型必须为随机访问迭代器。这意味着，sort() 只对 array、vector、deque 这 3 个容器提供支持。
如果对容器中指定区域的元素做默认升序排序，则元素类型必须支持<小于运算符；同样，如果选用标准库提供的其它排序规则，元素类型也必须支持该规则底层实现所用的比较运算符；
sort() 函数在实现排序时，需要交换容器中元素的存储位置。这种情况下，如果容器中存储的是自定义的类对象，则该类的内部必须提供移动构造函数和移动赋值运算符。

另外还需要注意的一点是，对于指定区域内值相等的元素，sort() 函数无法保证它们的相对位置不发生改变。实际场景中，如果需要保证值相等元素的相对位置不发生改变，可以选用 stable_sort() 排序函数。

头文件

#include <algorithm>

语法

//对 [first, last) 区域内的元素做默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

参数

参数	描述
first	随机访问迭代器
last	随机访问迭代器
comp	排序规则

案例

STL sort函数排序

使用 STL sort 函数实现排序

#include <iostream>   
#include <algorithm>  
#include <vector>
using namespace std;
bool mycomp(int i, int j) 
{
    return (i < j);
}
class mycomp2 
{
public:
    bool operator() (int i, int j) 
    {
        return (i < j);
    }
};
int main() 
{
	cout << "嗨客网(www.haicoder.net)\n" << endl;
    vector<int> myvector{ 11, 22, 10, 100, 23, 89, 1024 };
    sort(myvector.begin(), myvector.begin() + 4); 
    sort(myvector.begin(), myvector.begin() + 4, greater<int>()); 
    sort(myvector.begin(), myvector.end(), mycomp2());
    for (vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) 
    {
        cout << *it << ' ';
    }
    cout << endl;
    return 0;
}

我们在 Linux 下使用 g++ 进行编译，具体命令如下：

g++ sort.cpp -std=c++11

编译后，我们直接运行生成的二进制文件 a.out，如下图所示：

01_STL sort排序算法.png

可以看到，程序中分别以函数和函数对象的方式自定义了具有相同功能的 mycomp 和 mycomp2 升序排序规则。需要注意的是，和为关联式容器设定排序规则不同。

给 sort() 函数指定排序规则时，需要为其传入一个函数名（例如 mycomp ）或者函数对象（例如 std::greater<int>() 或者 mycomp2()）。

STL sort函数总结

C++ STL 标准库中的 sort() 函数，本质就是一个模板函数。该函数专门用来对容器或普通数组中指定范围内的元素进行排序，排序规则默认以元素值的大小做升序排序。

除此之外我们也可以选择标准库提供的其它排序规则（比如 std::greater<T> 降序排序规则），甚至还可以自定义排序规则。