[C++]std::sort()函数使用总结

函数声明

template< class RandomIt, class Compare >

constexpr void sort( RandomIt first, RandomIt last, Compare comp );

以一定排序规则排序指定范围内的元素，但是算法不具有稳定性，如果元素的值是相同的话不保证它们的相对顺序保持不变。

参数说明

first , last - 要排序的元素范围。

comp - 比较的函数，这里要满足compare的要求，如下：

总结下来一句话：就是在compare(int a ,int b)中，如果你想要从小到大排列，那么你需要的是 return a<b;（这里很简单，如果记不住的话，先随便按照一个方向写，最后发现反了的话改下大小于符号就行）

时间复杂度

平均 O(N·log(N)) 次比较，其中 N = std::distance(first, last) 。

我们需要注意的是sort()采用的是优化版本的快速排序，在最后阶段采用直接插入排序。因此时间复杂度为O(N·log(N))

举例说明

#include <algorithm>

#include <functional>

#include <array>

#include <iostream>

int main()

{

    std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; 

    // 用默认的 operator< 排序

    std::sort(s.begin(), s.end());

    for (auto a : s) {

        std::cout << a << " ";

    }

    std::cout << '\n';

    // 用标准库比较函数对象排序

    std::sort(s.begin(), s.end(), std::greater<int>());

    for (auto a : s) {

        std::cout << a << " ";

    }

    std::cout << '\n';

    // 用自定义函数对象排序

    struct {

        bool operator()(int a, int b) const

        {

            return a < b;

        }

    } customLess;

    std::sort(s.begin(), s.end(), customLess);

    for (auto a : s) {

        std::cout << a << " ";

    }

    std::cout << '\n';

    // 用 lambda 表达式排序

    std::sort(s.begin(), s.end(), [](int a, int b) {

        return b < a;

    });

    for (auto a : s) {

        std::cout << a << " ";

    }

    std::cout << '\n';

}

巴特西

[C++]std::sort()函数使用总结

函数声明

参数说明

时间复杂度

举例说明

最新文章

热门文章