如何对C++中的vector进行有效排序？

在计算机科学和编程中，排序是一个常见的操作，特别是在处理大量数据时。vector 是 C++ 标准模板库（STL）中的一个动态数组容器，它提供了一种方便的方式来存储和管理元素集合，本文将详细介绍如何使用vector 进行排序，包括不同的排序方法和相关示例。

使用 `std::sort` 函数

std::sort 是 C++ STL 提供的一个通用排序函数，它可以对vector 中的元素进行升序排序，默认情况下，std::sort 使用< 运算符来比较元素，如果需要降序排序，可以使用std::greater<>() 作为比较函数。

示例代码：

#include <iostream>
#include <vector>
#include <algorithm> // for std::sort
int main() {
    std::vector<int> vec = {5, 2, 9, 1, 5, 6};
    // 升序排序
    std::sort(vec.begin(), vec.end());
    // 输出排序后的 vector
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    // 降序排序
    std::sort(vec.begin(), vec.end(), std::greater<int>());
    // 输出排序后的 vector
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    return 0;
}

输出结果：

1 2 5 5 6 9 
9 6 5 5 2 1

2. 使用std::stable_sort 函数

std::stable_sort 是另一种排序函数，它在保持相等元素相对顺序的同时进行排序，这对于某些应用场景非常有用，比如当元素具有附加信息时。

示例代码：

#include <iostream>
#include <vector>
#include <algorithm> // for std::stable_sort
struct Person {
    std::string name;
    int age;
};
bool compareByAge(const Person &a, const Person &b) {
    return a.age < b.age;
}
int main() {
    std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 30}};
    // 稳定排序
    std::stable_sort(people.begin(), people.end(), compareByAge);
    // 输出排序后的 vector
    for (const auto &person : people) {
        std::cout << person.name << " " << person.age << std::endl;
    }
    return 0;
}

输出结果：

Bob 25
Alice 30
Charlie 30

自定义排序规则

除了使用默认的升序和降序排序外，还可以通过传递自定义的比较函数来实现特定的排序规则，可以按字符串长度对一组字符串进行排序。

示例代码：

#include <iostream>
#include <vector>
#include <algorithm> // for std::sort
bool compareByLength(const std::string &a, const std::string &b) {
    return a.length() < b.length();
}
int main() {
    std::vector<std::string> words = {"apple", "banana", "cherry", "date"};
    // 根据字符串长度排序
    std::sort(words.begin(), words.end(), compareByLength);
    // 输出排序后的 vector
    for (const auto &word : words) {
        std::cout << word << " ";
    }
    std::cout << std::endl;
    return 0;
}

输出结果：

date apple cherry banana

多关键字排序

有时需要根据多个关键字进行排序，这可以通过组合多个比较条件来实现，先按年龄排序，再按名字排序。

示例代码：

#include <iostream>
#include <vector>
#include <algorithm> // for std::sort
struct Person {
    std::string name;
    int age;
};
bool compareByAgeAndName(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> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 30}, {"David", 25}};
    // 多关键字排序
    std::sort(people.begin(), people.end(), compareByAgeAndName);
    // 输出排序后的 vector
    for (const auto &person : people) {
        std::cout << person.name << " " << person.age << std::endl;
    }
    return 0;
}

输出结果：

Bob 25
David 25
Alice 30
Charlie 30

FAQs

Q1:std::sort 和std::stable_sort 有什么区别？

A1:std::sort 是一种快速排序算法，它不保证相等元素的相对顺序保持不变，而std::stable_sort 则保证了这一点，即相等元素的相对顺序在排序后仍然保持不变。std::stable_sort 通常比std::sort 慢一些，因为它需要额外的空间来维护元素的稳定性。

Q2: 如何对包含自定义对象的vector 进行排序？

A2: 要对包含自定义对象的vector 进行排序，需要提供一个比较函数或比较仿函数，这个比较函数接受两个对象作为参数，并返回一个布尔值，指示第一个对象是否应该排在第二个对象之前，对于结构体Person，可以定义一个比较函数compareByAge，然后使用std::sort 函数进行排序。