STL sort算法中的比较函数

客官°小女子只卖身不卖艺 2022-07-16 09:20 204阅读 0赞

排序，既陌生又熟悉的名词。

排序，成为面试官中喜欢问的算法问题。

c++ STL中为我们提供了std::sort， 所以今天我们不是来描述各种排序算法的实现，而是看看怎么使用stl为我们提供的sort。

先预热，代码：

#include <algorithm>
    #include <iostream>
    #include <string>
    
    int main()
    {
        int test_arr[5];
        test_arr[0] = 2;
        test_arr[1] = 3;
        test_arr[2] = 5;
        atest_arrr[3] = 1;
        test_arr[4] = 4;
    
        std::sort(test_arr,test_arr+5);
    
        std::cout<<test_arr[0]<<"\n";
        std::cout<<test_arr[1]<<"\n";
        std::cout<<test_arr[2]<<"\n";
        std::cout<<test_arr[3]<<"\n";
        std::cout<<test_arr[4]<<std::endl;
    
        return 0;
    }

从输入结果可以看出，**sort默认是按照升序进行排序**。

**按照降序进行排序：**

#include <algorithm>
    #include <iostream>
    #include <string>
    #include <functional>
    
    int main()
    {
        int test_arr[5];
        test_arr[0] = 2;
        test_arr[1] = 3;
        test_arr[2] = 5;
        test_arr[3] = 1;
        test_arr[4] = 4;
    
        std::sort(test_arr,test_arr+5,std::greater<int>());
    
        std::cout<<test_arr[0]<<"\n";
        std::cout<<test_arr[1]<<"\n";
        std::cout<<test_arr[2]<<"\n";
        std::cout<<test_arr[3]<<"\n";
        std::cout<<test_arr[4]<<std::endl;
    
        return 0;
    }

其中用到了std::greater()。

**sort中使用迭代器：**

#include <vector>
    #include <algorithm>
    #include <iostream>
    #include <string>
    
    int main()
    {
        std::vector<int> test_vec;
        test_vec.push_back(2);
        test_vec.push_back(3);
        test_vec.push_back(5);
        test_vec.push_back(1);
        test_vec.push_back(4);
    
        std::sort(test_vec.begin(),test_vec.end());
    
        for(size_t i=0; i<test_vec.size(); ++i)
            std::cout<<test_vec[i]<<std::endl;
    
        return 0;
    }

**定义自己的比较函数–全局函数：**

#include <vector>
    #include <algorithm>
    #include <iostream>
    #include <string>
    
    class Person
    {
    public:
        // default constructor
        Person() : age(0) {}
        Person(int age, std::string name) {
            this->age = age; this->name = name;
        }
        int age;
        std::string name;
    };
    
    inline bool operator<(const Person& a, const Person& b)
    {
        return a.age < b.age;
    }
    
    int main()
    {
        std::vector<Person> persons;
        persons.push_back(Person(24,"Calvin"));
        persons.push_back(Person(30,"Benny"));
        persons.push_back(Person(28,"Alison"));
    
        std::sort(persons.begin(),persons.end());
    
        for(size_t i=0; i<persons.size(); ++i)
            std::cout<<persons[i].age<<", "<<persons[i].name<<std::endl;
    
        return 0;
    }

**定义自己的比较函数–成员函数：**

#include <vector>
    #include <algorithm>
    #include <iostream>
    #include <string>
    
    class Person
    {
    public:
        // default constructor
        Person() : age(0) {}
        Person(int age, std::string name) {
            this->age = age; this->name = name;
        }
        bool operator<(const Person& rhs)
        {
            return this->age < rhs.age;
        }
        int age;
        std::string name;
    };
    
    int main()
    {
        std::vector<Person> persons;
        persons.push_back(Person(24,"Calvin"));
        persons.push_back(Person(30,"Benny"));
        persons.push_back(Person(28,"Alison"));
    
        std::sort(persons.begin(),persons.end());
    
        for(size_t i=0; i<persons.size(); ++i)
            std::cout<<persons[i].age<<", "<<persons[i].name<<std::endl;
    
        return 0;
    }

**函数指针作为sort的比较函数：**

#include <vector>
    #include <algorithm>
    #include <iostream>
    #include <string>
    
    class Person
    {
    public:
        // default constructor
        Person() : age(0) {}
        Person(int age, std::string name) {
            this->age = age; this->name = name;
        }
    
        int age;
        std::string name;
    };
    
    bool Greater(const Person& a, const Person& b)
    {
        if(a.age == b.age)
            return a.name < b.name;
    
        return a.age > b.age;
    }
    
    int main()
    {
        std::vector<Person> persons;
        persons.push_back(Person(24,"Calvin"));
        persons.push_back(Person(30,"Benny"));
        persons.push_back(Person(30,"Alice"));
        persons.push_back(Person(28,"Alison"));
    
        std::sort(persons.begin(),persons.end(),Greater);
    
        for(size_t i=0; i<persons.size(); ++i)
            std::cout<<persons[i].age<<", "<<persons[i].name<<std::endl;
    
        return 0;
    }

**sort中使用lambda表达式：**

std::sort(persons.begin(), persons.end(), [](const Person &a, const Person &b) { return ((*a).age < (*b).age); });