sort自定义排序方式

• • sort()
  • • 方式1：结构体内重载运算符
    • 方式2：cmp参数
  • 与优先队列类比
  • Java和python的处理方式
  • • Java
    • python

sort(a.begin(), a.end());
sort(a, a + n); // n为数组长度
通常用于数组排序，排序方式为按照元素大小从小到大排序

当元素为结构体/pair等类型时，以及需要从大到小排序时，需要自定义。

对于结构体：
结构体按照某成员值，从小到大排序：
需要在结构体内重载运算符，从小到大重载<

// 按照val从小到大排序
struct Pair{
        int val, loc;
        // 结构体内重载运算符
        bool operator< (const Pair& t) const {
        	return val < t.val;
        }
    };
// pp为Pair类型的vector数组
sort(pp.begin(), pp.end()); // 按照val从小到大排序

结构体按照某成员值，从大到小排序：
需要在结构体内重载运算符，从大到小重载>

// 按照val从大到小排序
struct Pair{
        int val, loc;
        bool operator> (const Pair& t) const {
        	return val > t.val;
        }
    };
// pp为Pair类型的vector数组
sort(pp.begin(), pp.end(), greater()); // 按照val从大到小排序

结构体

// cmp参数
struct Pair{
    int val, loc;
};
bool cmp(Pair num1, Pair num2){ // 可能需要static (leetcode)
    return num1.val < num2.val;
}
sort(pp.begin(), pp.end(), cmp);// 数组或vector都可，cmp如上为从小到大排序；改为>即可从大到小排序

pair本质为结构体，同样也可

typedef pair PII;

static bool cmp(PII num1, PII num2){
    return num1.first < num2.first; // < 从小到大排序
}

vector pp;
sort(pp.begin(), pp.end(), cmp);

1. 一般的int数组：

priority_queue a; // 大根堆 
priority_queue, greater> b; // 小根堆

2. 对于pair

#include 
#include 
#include 
#include 

using namespace std;

int main(){
    typedef pair PII;
    // priority_queue p; // 大根堆
    // p.push({100, 2});
    // p.push({300, 2});
    // p.push({2, 300});
    // cout << p.top().first << " " << p.top().second << endl; // 300 2
    
    priority_queue, greater> p; // 小根堆
    p.push({100, 2});
    p.push({300, 2});
    p.push({1, 200});
    p.push({2, 300});
    cout << p.top().first << " " << p.top().second << endl; // 1 200
    
	return 0;
}

3. 对于结构体：

大根堆

struct Rec{
	int a, b;
	bool operator< (const Rec& t) const {// 有sort则必须运算符重载，具体：小根堆重载>，大根堆重载＜
		return a < t.a;
	}
};

priority_queue d; // 大根堆重载＜，此处为大根堆

小根堆

struct Rec{
	int a, b;
	bool operator> (const Rec& t) const {// 有sort则必须运算符重载，具体：小根堆重载>，大根堆重载＜
		return a > t.a;
	}
};

priority_queue, greater> d; // 小根堆重载>，此处为小根堆

e.g.

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1010;

int main(){
    // struct Person{
    //     int a, b;
    //     bool operator< (const Person& t) const{
    //         return a < t.a;
    //     }
    // };
    
    // priority_queue p; // 大根堆
    // p.push({100, 2});
    // p.push({300, 2});
    // p.push({2, 300});
    // cout << p.top().a << " " << p.top().b << endl; // 300 2
    
    struct Person{
        int a, b;
        bool operator> (const Person& t) const{
            return a > t.a;
        }
    };
    
    priority_queue, greater> p; // 小根堆
    p.push({100, 2});
    p.push({300, 2});
    p.push({2, 300});
    cout << p.top().a << " " << p.top().b << endl; // 2 300
	
	return 0;
}

另外，对于复杂元素的排序，整理Java和python的处理方式：

以1009: 1-2-1 Milking Cows 挤牛奶为例，
基本思路是先转为列表List<>，再通过Collections.sort()处理：

Collections.sort(list, new Comparator<单个元素的类型>() {
            //升序排序 若降序则交换o1,、o2顺序即可
            public int compare(元素类型 o1,
                               元素类型 o2) {
                return o1.getKey().compareTo(o2.getKey()); // 此处为元素的key或者其他属性值
            }

        });

完整代码：

import java.util.*;

public class Main{
    public static int N = 5010;
    public static int n;
    public static int a, b;
    public static Map map = new HashMap<>();

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for(int i = 0; i < n; i ++ ){
            a = scanner.nextInt();b = scanner.nextInt();
            map.put(a, b);
        }
        // 对map的key进行排序(左端点)
        List> listOfMap = new ArrayList>(map.entrySet());// 取出集合再化为列表
        Collections.sort(listOfMap, new Comparator>() {
            //升序排序
            public int compare(Map.Entry o1,
                               Map.Entry o2) {
                return o1.getKey().compareTo(o2.getKey());
            }

        });
//        System.out.println(listOfMap);
        Map.Entry first = listOfMap.stream().findFirst().orElse( null );
//        System.out.println(first);
        // 贪心
        int res1 = 0, res2 = 0;
        int l = first.getKey(), r = first.getValue();
        for(Map.Entry item:listOfMap){
            if(item.getKey() <= r) r = Math.max(r, item.getValue());
            else{
                res1 = Math.max(res1, r - l);
                res2 = Math.max(res2, item.getKey() - r);
                l = item.getKey();
                r = item.getValue();
            }
        }
        res1 = Math.max(res1, r - l); // 最后一段别漏了
        System.out.println(res1 + " " + res2);
    }
}

eg：p列表中的元素x也为列表，按照x的第一个元素进行排序：

p = sorted(p, key = lambda x : x[0])