C++ 容器的排序算法_c++容器排序

1. 概念

1.1 了解下方所有关于sort算法函数的作用

1.2 STL提供的关系类仿函数列表

1.3 注意事项

map不支持sort排序，sort只支持数组、vetctor等的排序，如果需要对map进行排序，则要将其转换成数组。
c++ map按value值排序

2. 应用——对vector容器的sort算法

2.1 容器中元素是一些标准类型int、float、char或者string时

这种情况也是最简单的情况，以下举出最常用的几个例子：

// vector 从小到大排序
sort(v.begin(), v.end());
// vector 从大到小排序
sort(v.begin(), v.end(), greater<int>());
// array 从小到大排序
sort(a, a + 3);
// array从大到小排序
sort(a, a + 3, greater<int>());
1
2
3
4
5
6
7
8

/*
 * @Description: STL仿函数列表的应用，包括sort排序
 * @Author: CM
 * @Date: 2021-03-25 10:31:45
 * @LastEditTime: 2021-03-25 16:37:38
 * @LastEditors: CM
 */
#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
using namespace std;

/**STL仿函数列表
 * 名称              |描述
 * ----------------------------------              
 * less             |从小到大排序(<)
 * greater          |从大到小排序(>)
 * ----------------------------------
 * less_equal       |小于等于(<=)
 * greater_equal    |大于等于(>=)
 * equal_to         |等于(==)
 * not_equal_to     |不等于(!=)
 */

void test01()
{
 /* --------------------less和greater用于sort排序----------------------------- */
    vector<int> v;
    v.push_back(10);
    v.push_back(30);
    v.push_back(50);
    v.push_back(30);
    v.push_back(20);
    cout << "before sort" << endl;
    /* 10 30 50 30 20 */
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
  
    // sort(v.begin(), v.end());                /*  10 20 30 30 50 */
    // sort(v.begin(), v.end(), less<int>());   /* less<int>()： 10 20 30 30 50 */
    // sort(v.begin(), v.end(), greater<int>());   /* greater<int>()： 50 30 30 20 10  */
    sort(v.rbegin(), v.rend());                 /*  50 30 30 20 10  */
    
    cout << "after sort" << endl;
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
/* -------------------------全部关系仿函数的应用----------------------------- */

    cout << less<int>()(3, 5) << endl;           /* 1 */
    cout << greater<int>()(3, 5) << endl;        /* 0 */
    cout << less_equal<int>()(3, 5) << endl;     /* 1 */
    cout << greater_equal<int>()(3, 5) << endl;  /* 0 */
    cout << equal_to<int>()(3, 5) << endl;       /* 0 */
    cout << not_equal_to<int>()(3, 5) << endl;   /* 1 */
    
}

int main() {
    test01();
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

2.2 自定义类型按照其他方式排序（类、包含对组的容器）

2.2.1 vector<myclass>(运算符的重载）

“sort()”的两种排序规则的定义：

1. 通过重载逻辑运算符"<"，使用一次sort可以完成排序

   class myclass {
   public:
   	myclass(int a, int b):first(a), second(b){}
   	int first;
    	int second;
   	bool operator < (const myclass &m) const {
           return first < m.first;
   	}
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9

2. 通过定义逻辑函数"compare"，sort的第三个参数加上该逻辑函数

   bool less_second(const myclass & m1, const myclass & m2) {
       return m1.second < m2.second;
   }
   1
   2
   3

/*
 * @Description: 摘自https://blog.csdn.net/steft/article/details/53170502?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161658741416780266290555%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161658741416780266290555&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-53170502.first_rank_v2_pc_rank_v29_10&utm_term=vector%E5%AE%B9%E5%99%A8%E7%9A%84%E6%8E%92%E5%BA%8F
 */
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

class myclass {
public:
    myclass(int a, int b):first(a), second(b){}
    int first;
    int second;
    bool operator < (const myclass &m) const {
            return first < m.first;
    }
    /* 复习常成员函数：
    * 1. 只能引用本类的数据成员，而不能修改他们（可以引用const数据成员，也可以引用非const数据成员） 
    * 2. 在声明和定义时要有const,调用时不用
    * */
};

bool less_second(const myclass & m1, const myclass & m2) {
        return m1.second < m2.second;
}

int main() {
        
        vector< myclass > vect;
        for(int i = 0 ; i < 10 ; i ++){
            myclass my(10-i, i*3);
            vect.push_back(my);
        }
        for(int i = 0 ; i < vect.size(); i ++) 
            cout<< "("<< vect[i].first << "," << vect[i].second <<")\n"; 

        /* 1. 自己写比较函数,将类中的第二个值从大到小排序*/
        sort(vect.begin(), vect.end(), less_second);
        cout <<"自己写比较函数,将类中的第二个值从小到大排序："<<endl;
        for(int i = 0 ; i < vect.size(); i ++) 
            cout<< "(" << vect[i].first << "," << vect[i].second <<")\n";

        /* 2. 重载类型的'<'操作赋，先留一个坑 */
        sort(vect.begin(), vect.end());
        cout << "重载运算符，将类中的第一个值从大到小排序：" << endl;
        for(int i = 0 ; i < vect.size(); i ++) 
            cout<< "(" << vect[i].first << "," << vect[i].second << ")\n";
               
        return 0 ;
}
/* 运行结果
(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
自己写比较函数,将类中的第二个值从小到大排序：
(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
重载运算符，将类中的第一个值从大到小排序：
(1,27)
(2,24)
(3,21)
(4,18)
(5,15)
(6,12)
(7,9)
(8,6)
(9,3)
(10,0)
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

2.2.2 vector<pair<string, int>>（main函数中对组）

/*
 * @Description: 对包含对组的vector容器进行自定义排序
 * @Author: CM
 * @Date: 2021-03-25 11:22:24
 * @LastEditTime: 2021-03-25 18:52:19
 * @LastEditors: CM
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

bool cmp(const pair<string, int> & v1, const pair<string, int> & v2) {
    return v1.second < v2.second;
}

int main() {
    vector<pair<string, int>> v;
    v.push_back(make_pair("xixi", 3));
    v.push_back(make_pair("haha", 1));
    v.push_back(make_pair("lala", 2));
    v.push_back(make_pair("gugu", 4));

    for(vector<pair<string, int>>::iterator it = v.begin(); it != v.end(); it++) {
        cout << (*it).first << " " << (*it).second << " ";
    }
    cout << endl;
    /* xixi 3 haha 1 lala 2 gugu 4 */

    sort(v.begin(), v.end());
    for(vector<pair<string, int>>::iterator it = v.begin(); it != v.end(); it++) {
        cout << (*it).first << " " << (*it).second << " ";
    }
    cout << endl;
    /* gugu 4 haha 1 lala 2 xixi 3 默认情况是按照vector容器中第一个元素排序(pair类型放入优先队列中总是先比较first的大小,相同在比较second的大小)*/

    /* 自己写比较函数 */
    sort(v.begin(), v.end(), cmp);
    for(vector<pair<string, int>>::iterator it = v.begin(); it != v.end(); it++) {
        cout << (*it).first << " " << (*it).second << " ";
    }
    cout << endl;
    /* haha 1 lala 2 xixi 3 gugu 4 */

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

2.2.3 vector<vector<int>>（定义在同一类中）

来源：406. 根据身高重建队列

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> que;
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);
        }
        return que;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

为什么加static?类内sort自定义排序函数需定义为static否则报错

3. 参考链接

1. 对vector等STL标准容器进行排序操作.
2. C++ sort vector<vector > or vector 容器的排序.
3. pair类型在priority_queue中是如何排序的.
4. 优先队列 以及 sort对 pari 的自定义排序.