首页std::sort详解

std::sort详解

时间: 2023-07-24 17:20:34 浏览: 266

std::sort是C++ STL中的一个排序算法，可用于对数组、向量和其他序列容器中的元素进行排序。其函数原型如下： ```c++ template< class RandomIt > void sort( RandomIt first, RandomIt last ); template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare comp ); ``` 其中，第一个参数是指向待排序序列的起始位置的迭代器，第二个参数是指向待排序序列的末尾位置的迭代器。第二个函数原型中，第三个参数是一个比较函数，用于定义排序规则。 std::sort使用快速排序算法进行排序，其时间复杂度为O(nlogn)，空间复杂度为O(logn)。快速排序算法的基本思想是选取一个元素作为枢轴，将序列中小于枢轴的元素移到枢轴的左边，大于枢轴的元素移到枢轴的右边，然后对左右两个子序列分别递归进行排序。 std::sort默认按升序排序，如果需要按降序排序，则需要自定义一个比较函数，例如： ```c++ bool cmp(int a, int b) { return a > b; } int main() { vector<int> v = {3, 2, 1, 4, 5}; sort(v.begin(), v.end(), cmp); for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } return 0; } ``` 此时输出结果为：5 4 3 2 1。

阅读全文