sort的自定义排序与lambda表达式

今天在刷力扣讨论区时，看到一个问题，是关于C++sort()函数自定义排序的：知识点提问｜关于 C++ 的 sort 的自定义排序 - 力扣，正好也用过很多次了，就试着回答了一下，没想到被精选了😂😂，还得了150积分。

力扣积分

于是想了想，准备将那个回答完善一下，也放到这里来。

sort函数的介绍

sort()函数位于<algorithm>头文件中，大概是最常用的泛型算法之一了。顾名思义，这是用来排序的函数。它的一般形式为sort(iterator first,iterator last)，将[first,last)中的元素按升序排列。由于容器支持的迭代器类型必须为随机访问迭代器，sort() 只支持array、vector、deque 这 3 个容器。

应该说，大部分情况下，选择sort()函数进行排序是简单且高效的。sort对普通的快速排序进行了优化，并结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。它的时间复杂度是O(N*log2N)。这比随便写一个O(N^2)的冒泡排序好太多了。也避免了手写快排的麻烦。

自定义排序方法

sort()默认是升序的，那么，如果我们希望降序排列，或者是按绝对值大小排列，或者是其他各种各样的排序方式，又该怎么办呢？为此，sort()提供了第二个版本sort(iterator first,iterator last,cmp)。很多泛型算法都允许重载它的操作符，而sort()的操作符就是<，或者，更通俗地说，就是排在前面。也就是说，我们可以自定义排在前面的判断方式。具体方法是利用这样一个函数：bool cmp(auto &a,auto &b){...}，如果返回true，就代表a应该排在b前面，否则是b在a前，然后sort就根据我们定义的比较方式进行排列。例如，如果我们希望降序排列，就返回a>b即可。

举个例子：加入我们希望按照元素的绝对值排序，可以这么写

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool cmp(int a,int b)//按绝对值升序排列的比较函数
{
    return abs(a)<abs(b);
}
int main()
{
    vector<int> nums;
    int n;
    while(cin>>n) nums.push_back(n);
    sort(nums.begin(),nums.end(),cmp);//自定义的排序方式
    for(int i:nums) cout<<i<<" ";
    return 0;
}

输入：1 2 3 -4 -7 -3 5 -8 6，输出：1 2 3 -3 -4 5 6 -7 -8

这样，每次排序都要在外面定义一个cmp函数，然后在排序时调用它。然而，这是有缺陷的。一来，不直观，我们阅读代码时，只看到一个cmp，还要到外面去找它，如果排序次数很多，这么多函数很容易混淆。不过，更致命的是，这样定义的函数只能接受两个参数，就是比较的双方。试想一下，假如我们要根据b数组中元素的大小，来对a数组进行排序，那该怎么办呢？只好把b变成全局的，不但麻烦，而且可能无法操作。

使用lambda函数代替`cmp`

从这两个方面，可以看出lambda表达式的优越性了。它的结构是这样的：[capture list](parameter list) ->return type {function body}其中，parameter list(参数列表)和function body(函数体)与上面的cmp函数没有什么差异。return type虽说必须尾置，但通常可以省略。而capture list(捕获列表)中可以填写作用域中的参数，使它在lambda表达式内部可见。这就解决了上面的第二个问题。比如说，我们要捕获b数组，就写成[&b]即可(&代表引用捕获)，也就是说捕获列表使lambda表达式可以使用不限量的外部参数，当然，如果不想指定捕获哪些，直接写[&]，就是全部引用捕获。同时，哪里用到，就写在哪里，还不用起名字(所以也叫匿名函数)，使它既直观又方便。

例如：我们根据flag数组中的元素大小，来对index数组(index对应着flag的下标)进行排序，可以这么写

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    vector<int> flag  = {2,3,5,4,1,8,7,9,6};
    vector<int> index = {0,1,2,3,4,5,6,7,8};
    sort(index.begin(),index.end(),[&flag](int a,int b){return flag[a]<flag[b];});
    for(int i:index)
        cout<<i<<" ";
    return 0;
}

输出：4 0 1 3 2 8 6 5 7

力扣857题的排序，就用到了这种方法。

最后，再列举几种常见的排序方式和使用它们的题目。

1.按照string的长度对string序列排序

sort(vec.begin(),vec.end(),[](auto &s1,auto &s2){return s.size()<s2.size();});

在648. 单词替换 - 力扣中使用到了。

2.按照pair的second大小降序排序，如果相同再按first升序排序

sort(vec.begin(),vec.end(),[](auto &p1,auto &p2){return p1.second==p2.second?p1.first<p2.first:p1.second>p2.second;})

这种排序方法常见于利用哈希表统计词频后的排序过程。

在1636. 按照频率将数组升序排序和451. 根据字符出现频率排序中使用了类似的排序方法。

lambda表达式当然不仅仅可以用在排序里，剩下的用法可以慢慢去发掘😂。

以上主要是参照了《C++ Primer第五版》P346-353的内容，以及我自己的一些理解。时间所限，表述和代码或许有不完备、不正确的地方，欢迎交流斧正。

9.25更新

神奇的事发生了，就在这周，周赛的第一题就出现了我上面举的例子。传送门。恰恰就是利用A数组，给B数组排序，估计是出题人看到了我的回答，精选的同时作为题目储备了吧。当然，这无疑是一道简单题(数据范围也只有1e3)，评论区也出现了好多种方法。甚至还有冒泡排序……不过，对于c++来说，时空复杂度综合最小的就应该是上述的方法了(组成pair再用lambda表达式排序空间消耗更大，而模拟冒泡排序虽然没有新建数组，但时间复杂度达到了O(N^2))。具体代码如下

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        vector<int> flag;
        for(int i=0;i<names.size();++i)
            flag.push_back(i);
        sort(flag.begin(),flag.end(),[&](int a,int b){return heights[a]>heights[b];});
        vector<string> ans;
        for(int i:flag)
            ans.push_back(names[i]);
        return ans;
    }
};