6-5 通讯录排序

题目描述：

给定n个人的通讯录信息，包括姓名、电话、地址和邮编。按照以下标准输出通讯录信息：

- 按照姓名的字典序从小到大排序。
- 对于姓名相同的人，按照电话号码的字典序从小到大排序。
- 对于电话号码相同的人，按照地址的字典序从小到大排序。
- 对于地址相同的人，按照邮编的字典序从小到大排序。

输入格式：

输入第一行给出正整数n（<=10000）；第二行至第n+1行按照“姓名 电话 地址 邮编”的格式给出每个人的通讯录信息。题目保证每个人的信息是唯一的。

输出格式：

按照给定排序规则输出每个人的信息，即按照姓名非降序输出；若姓名相同，则按照电话号码非降序输出；以此类推。每个人的信息占一行，用1个空格分隔。如果数据存在多解，则按照输入顺序输出。

输入样例：

4

Tom 1234567 Shanghai 200030

Jerry 2345678 Beijing 100000

John 2345678 Shanghai 200030

Jim 87654321 Shanghai 300000

输出样例：

Jerry 2345678 Beijing 100000

John 2345678 Shanghai 200030

Jim 87654321 Shanghai 300000

Tom 1234567 Shanghai 200030

算法1：

(字典序排序) $O(nlogn)$

思路：按规则排序，使用sort排序

时间复杂度

$O(nlogn)$

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Person {
    string name, phone, address, postCode;
};

bool cmp(const Person& a, const Person& b) {
    if (a.name != b.name) return a.name < b.name;
    if (a.phone != b.phone) return a.phone < b.phone;
    if (a.address != b.address) return a.address < b.address;
    return a.postCode < b.postCode;
}

int main() {
    int n;
    cin >> n;
    vector<Person> persons(n);
    for (int i = 0; i < n; i++) {
        cin >> persons[i].name >> persons[i].phone >> persons[i].address >> persons[i].postCode;
    }
    sort(persons.begin(), persons.end(), cmp);
    for (int i = 0; i < n; i++) {
        cout << persons[i].name << " " << persons[i].phone << " " << persons[i].address << " " << persons[i].postCode << endl;
    }
    return 0;
}