C++ 中的排序以及自定义排序

2022年11月6日 29点热度 0人点赞 0条评论

sort 函数可以三个参数也可以两个参数, 必须的头文件 #include < algorithm>using namespace std;

它使用的排序方法是类似于快排的方法, 时间复杂度为 $n\log n$

两个参数的 sort 默认升序排序

(a>b 说明 a 比 b 大的时候排在 b 的前面)

返回值为 true, 则代表比较的两个数不进行交换, 为 false 则进行交换. 一句话: 符号与规则一致. 想要从小到大的顺序, 则为 < 号, 想要从大到小的规则, 则使用 >.

使用运算符重载:
默认比较方式按'<'来执行
返回值为 true, 则代表比较的两个数不进行交换, 为 false 则进行交换.
这种方法, 一般用于结构体比较. 普通类型一般不适用这么复杂的.

但是对于 priority_queue 当返回值为 true 时, 进行交换, 但为 false 时不进行交换. 同样对于基本类型传入 less 是大根堆, 从小到大排序. 传入 greater 是小根堆, 从大到小排序. 这是由底层代码决定的.

前置知识 (重中之重)

在 STL 中我们一般有两种自定义排序的方式, 一种是对 sort 的排序规则进行自定义, 一种是对 STL 容器自己的排序规则进行自定义, 这两种方式的区别在于:

  • 对 sort 函数进行自定义的时候既可以使用仿函数 (必须是谓词) 也可以使用普通函数
  • 对 STL 容器自己的排序规则进行自定义的时候, 只能使用仿函数, 因为 C++的模板编程需要传入模板类型而不是函数指针, 所以自定义的普通函数在这里是无效的.
  • 使用仿函数的时候, 函数声明后面函数体前面必须加上 const, 将该函数设置为常量成员函数, 表示该函数的隐含 this 指针被设置为了 const 指针, 即无法在该函数内修改成员变量的值.(只读模式) 有关于这一部分可以参照 这里

使用自定义比较器

bool cmp(const int a, const int b){
    return a < b;
}
int main(){
    int arr[] = {2, 6,3,5,4,8,1,0,9,10};
    sort(arr, arr+10, cmp);
    for(int i = 0;i < 10;i++)
        cout << arr[i] << " ";
}
// out
/*
0 1 2 3 4 5 6 8 9 10
*/

使用 lambda 表达式自定义比较器

int main(){
    int arr[] = {2, 6,3,5,4,8,1,0,9,10};
    sort(arr, arr+10, [](const int a, const int b){
         return a < b;
         });
    for(int i = 0;i < 10;i++)
        cout << arr[i] << " ";
}
// out
/*
0 1 2 3 4 5 6 8 9 10
*/
sort(mMyClassVector.begin(), mMyClassVector.end(), 
    [](const MyClass & a, const MyClass & b) -> bool
{ 
    return a.mProperty > b.mProperty; 
});
sort(test.begin(), test.end(),[](A x, A y){return x.a>y.a;});

C++ lambda 以及 sort

语法

[ capture list ] ( parameter list) -> return type { function body; };
[捕获列表]( 参数列表 ) -> 返回值类型{函数体}

参数列表和返回类型可以为空, 但是捕获列表和函数体不能为空

auto f = []{return 42};
auto f = [](int a) -> int { return a + 1; };
std::cout << f(1) << std::endl;  // 输出: 2

捕获列表
[] 不捕获任何变量.
[&] 捕获外部作用域中所有变量, 并作为引用在函数体中使用 (按引用捕获).
[=] 捕获外部作用域中所有变量, 并作为副本在函数体中使用 (按值捕获).
[=,&foo] 按值捕获外部作用域中所有变量, 并按引用捕获 foo 变量.
[bar] 按值捕获 bar 变量, 同时不捕获其他变量.
[this] 捕获当前类中的 this 指针, 让 lambda 表达式拥有和当前类成员函数同样的访问权限. 如果已经使用了 & 或者 =, 就默认添加此选项. 捕获 this 的目的是可以在 lamda 中使用当前类的成员函数和成员变量.

在 sort 中的用法, 在 leetcode 题解中看到的, 使用 lambda 表达式自定义排序规则.

sort(people.begin(), people.end(), [](const vector<int>& u, const vector<int>& v) {
   return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
 });

有关知识点可看 https://blog.csdn.net/u013390476/article/details/50424995

默认状态下, sort 只有两个参数, 默认按照 vector 中的对象 operator< 即从小到大排列.
第三个参数可以是一个谓词, 自定义排序规则.
谓词可以是一个函数指针, 此函数有两个参数, 返回 bool 值, 即比较两个对象, 想要的顺序就返回 ture.
谓词还可以是 lambda, 来自定义排序规则.

二维 vector 排序

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (int i = 0; i < intervals.size(); ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (!merged.size() || merged.back()[1] < L) {
                merged.push_back({L, R});
            }
            else {
                merged.back()[1] = max(merged.back()[1], R);
            }
        }
        return merged;
    }
};

作者:LeetCode-Solution
链接:https://leetcode.cn/problems/SsGoHC/solution/he-bing-qu-jian-by-leetcode-solution-ghjl/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

rainbow

没什么大用的码农; 贴图怪; bug制造者; 只会电脑开关机的开发;

文章评论