【C++】使用sort函数进行容器排序

原创

adamtian

发布于 2020-10-11 00:51:42

2.9K0

发布于 2020-10-11 00:51:42

文章被收录于专栏：C++学习笔记

今天刷leetcode时遇到一个需要对vector<vector<int>>类型的二维数组进行排序，记录一下怎么使用sort函数对这种容器的元素进行排序，如何做到性能最优。

sort函数的基本用法

首先sort函数对于基础数据类型是支持默认的比较函数的，对于高级数据结构，如容器、自定义类的对象等排序需要自定义比较函数，作为第三个参数传递给sort函数。

STL中sort函数的原型如下：

// 默认
  template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
// 自定义
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

简单的使用，默认是升序排列：

vector<int> v = {2, 0, 1, 5, 9, 2, 7};
sort(v.begin(), v.end()); // 等价于下面
sort(v.begin(), v.end(), less<int>());

// 如果需要降序排序
sort(v.rbegin(), v.rend());
sort(v.begin(), v.end(), greater<int>());

如果希望使用降序排列，可以借助迭代器的反转属性，或者使用大于的仿函数。除greater以外，STL还提供了其他仿函数，如equal_to, not_equal_to, less_equal, greater_equal 等。

容器元素的排序

当数组的元素不是基础数据类型时，我们需要自定义比较函数。特别地，对于二维数组可以直接调用sort函数，默认是按照第一列的元素进行排序的。

/* Input matrix
m = [
        1 4 2 
        0 8 3
        3 5 1
    ]
*/

// Ascending order by first column
sort(m.begin(), m.end());
/*
m = [
        0 8 3
        1 4 2 
        3 5 1
    ]
*/

// Descending order by first column
sort(m.rbegin(), m.rend());
/*
m = [
        3 5 1
        1 4 2 
        0 8 3
    ]
*/

如果我们希望按照第2列或者第n列进行排序，有下面两种方式：

sort(m.begin(), m.end(), [](const vector<int> &a, const vector<int> &b) { return a[1] < b[1]; } );

bool cmp(const vector<int> &a, const vector<int> &b) {
    return a[1] > b[1];
}
sort(m.begin(), m.end(), cmp);

如果数组元素是自定义类的话，只能通过定义比较函数来完成排序：

class MyClass {
public:
    string name;
    int age;
    A(string name, int age): name(name), age(age) {}
 };
 
 // 按照年龄升序排列
 bool cmp(MyClass &a, MyClass &b) {
     return a.age < b.age;
 }
 // 使用
 vector<MyClass> vec;
 vec.push_back(MyClass("adam",12));
 vec.push_back(MyClass("Tom", 1));
 vec.push_back(MyClass("Bob", 5));
 
 sort(vec.begin(), vec.end(), cmp);

sort函数性能优化

TODO

排序的拓展

这里聊一下另外一个非常有用的排序函数，nth_element 用于指定元素排序。之前没有用过这个函数，直到有一次在工作提交代码时看到有人用这个函数，就去搜索了一下。

它不需要对整个数组完全排序，只要按照第n个元素进行排序，左边的比它小，右边的比它大即可，反之亦然。

template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, StrictWeakOrdering comp);

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

c++

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

c++

登录后参与评论

0 条评论

热度