c++如何对vector进行排序_c++ vector容器排序算法指南-C++-PHP中文网

最直接高效的方法是使用std::sort，它默认升序排序，支持自定义比较器如Lambda表达式实现降序或复杂对象的多条件排序，还可结合std::greater实现逆序；对于需保持相等元素顺序的场景可用std::stable_sort，只需部分有序时可用std::partial_sort，仅定位第K个元素时推荐std::nth_element以提升性能。

c++如何对vector进行排序_c++ vector容器排序算法指南

在C++中，对std::vector进行排序最直接、最常用且通常也是最高效的方法，是利用标准库中<algorithm>头文件提供的std::sort函数。它能以默认的升序方式，或者根据你提供的自定义比较规则，轻松地重新排列vector中的元素。

解决方案

std::sort是C++标准库中的一个强大工具，它接受两个迭代器作为参数，定义了要排序的范围。默认情况下，它会使用元素的operator<进行升序排序。

假设我们有一个整数vector：

#include <vector>
#include <algorithm> // 包含 std::sort
#include <iostream>  // 用于输出

void printVector(const std::vector<int>& vec, const std::string& label) {
    std::cout << label << ": ";
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    printVector(numbers, "原始数据");

    // 1. 默认升序排序 (使用元素类型的operator<)
    std::sort(numbers.begin(), numbers.end());
    printVector(numbers, "升序排序后"); // 输出: 1 2 3 4 5 6 7 8 9

    // 2. 降序排序
    // 方法一：使用 std::greater<T>() 函数对象
    std::vector<int> numbers_desc = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    std::sort(numbers_desc.begin(), numbers_desc.end(), std::greater<int>());
    printVector(numbers_desc, "降序排序 (std::greater)"); // 输出: 9 8 7 6 5 4 3 2 1

    // 方法二：使用 Lambda 表达式 (更灵活，推荐)
    std::vector<int> numbers_lambda_desc = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    std::sort(numbers_lambda_desc.begin(), numbers_lambda_desc.end(), [](int a, int b) {
        return a > b; // 如果a大于b，则a排在b前面
    });
    printVector(numbers_lambda_desc, "降序排序 (Lambda)"); // 输出: 9 8 7 6 5 4 3 2 1

    return 0;
}

登录后复制

std::sort通常采用内省式排序（Introsort），这是一种混合排序算法，结合了快速排序、堆排序和插入排序的优点，因此在大多数情况下都能提供O(N log N)的平均时间复杂度，并且在最坏情况下也能保持这一复杂度。我个人觉得，对于日常的vector排序需求，std::sort几乎是你的不二之选，除非你有非常特殊的稳定性或性能要求。

立即学习“C++免费学习笔记（深入）”；

C++ `vector`排序有哪些常见方法？

除了上面提到的默认升序和使用std::greater<T>()进行降序排序外，我们最常遇到的就是需要自定义排序规则的场景。这通常涉及到对复杂对象或根据多个条件进行排序。

使用Lambda表达式： 这是现代C++中最推荐和最灵活的方式。你可以直接在std::sort的第三个参数位置，编写一个匿名函数来定义你的比较逻辑。

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

struct Product {
    std::string name;
    double price;
    int stock;
};

void printProducts(const std::vector<Product>& products, const std::string& label) {
    std::cout << label << ":\n";
    for (const auto& p : products) {
        std::cout << "  Name: " << p.name << ", Price: " << p.price << ", Stock: " << p.stock << std::endl;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<Product> products = {
        {"Laptop", 1200.0, 10},
        {"Mouse", 25.0, 100},
        {"Keyboard", 75.0, 50},
        {"Monitor", 300.0, 10},
        {"Webcam", 25.0, 20}
    };
    printProducts(products, "原始产品列表");

    // 按价格升序排序
    std::sort(products.begin(), products.end(), [](const Product& a, const Product& b) {
        return a.price < b.price;
    });
    printProducts(products, "按价格升序排序");

    // 按库存降序排序，如果库存相同，则按名称升序排序
    std::sort(products.begin(), products.end(), [](const Product& a, const Product& b) {
        if (a.stock != b.stock) {
            return a.stock > b.stock; // 库存多的在前
        }
        return a.name < b.name; // 库存相同，按名称字母顺序
    });
    printProducts(products, "按库存降序，库存相同按名称升序排序");
    return 0;
}

登录后复制

Lambda表达式的简洁性和内联特性，让它在处理这类自定义排序时显得格外方便。

使用函数对象（Functor）： 创建一个重载了operator()的类，其行为类似于一个函数。这在比较逻辑复杂，或者需要在多个地方复用同一比较逻辑时很有用。
```
struct CompareProductsByPrice {
    bool operator()(const Product& a, const Product& b) const {
        return a.price < b.price;
    }
};

// ...在main函数中...
std::sort(products.begin(), products.end(), CompareProductsByPrice());
```
登录后复制
虽然现在Lambda表达式用得更多，但理解函数对象的工作原理对理解STL算法的底层机制还是很有帮助的。
使用普通函数： 你也可以定义一个普通的全局函数或静态成员函数作为比较器。
```
bool compareProductsByName(const Product& a, const Product& b) {
    return a.name < b.name;
}

// ...在main函数中...
std::sort(products.begin(), products.end(), compareProductsByName);
```
登录后复制
这种方式在C++11之前比较常见，现在通常被Lambda表达式取代，因为它避免了额外的函数定义。

在我看来，掌握Lambda表达式的用法是关键，它几乎可以满足所有自定义排序的需求，并且代码可读性很好。

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

554

查看详情

如何对自定义类型或复杂对象构成的`vector`进行排序？

对自定义类型进行排序，核心在于告诉std::sort如何比较两个对象。有两种主要策略：

重载operator<： 如果你的自定义类型有明确的“小于”关系，并且这种关系是该类型的主要比较方式，那么重载operator<是最佳选择。一旦你重载了它，std::sort就可以在不提供任何额外比较器的情况下直接使用你的类型。

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

struct Student {
    std::string name;
    int score;
    int id;

    // 重载 operator<
    // 默认按分数降序，分数相同按ID升序
    bool operator<(const Student& other) const {
        if (score != other.score) {
            return score > other.score; // 分数高的排前面 (降序)
        }
        return id < other.id; // 分数相同，ID小的排前面 (升序)
    }
};

void printStudents(const std::vector<Student>& students, const std::string& label) {
    std::cout << label << ":\n";
    for (const auto& s : students) {
        std::cout << "  Name: " << s.name << ", Score: " << s.score << ", ID: " << s.id << std::endl;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 95, 101},
        {"Bob", 88, 102},
        {"Charlie", 95, 103},
        {"David", 72, 104},
        {"Eve", 88, 105}
    };
    printStudents(students, "原始学生列表");

    // 直接调用 std::sort，它会使用 Student::operator<
    std::sort(students.begin(), students.end());
    printStudents(students, "排序后 (按分数降序，分数相同按ID升序)");

    return 0;
}

登录后复制

重载operator<的好处是代码简洁，符合直觉。但缺点是，如果你需要多种不同的排序方式（例如，有时按分数升序，有时按名字字母顺序），你就不能只依赖一个operator<了。

提供自定义比较器（Lambda、函数对象、普通函数）： 当你需要多种排序方式，或者你的类型不适合定义一个唯一的“小于”关系时，提供一个外部比较器是更灵活的方案。这和上一节提到的方法是完全一致的。你只需要确保你的比较器函数或Lambda接受两个你的自定义类型的const引用，并返回一个bool值，表示第一个参数是否应该排在第二个参数之前。
```
// 假设 Student 没有重载 operator<
// 我们可以用Lambda按名字升序排序
// ...在main函数中...
std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    return a.name < b.name;
});
printStudents(students, "按名字升序排序");
```
登录后复制
在我看来，对于复杂对象，如果存在一个“自然”的排序顺序，重载operator<是优雅的选择。但如果排序需求多变，或者对象的比较逻辑很复杂，我更倾向于使用Lambda表达式作为std::sort的第三个参数，因为它能让我直接在调用点定义排序规则，清晰明了。

除了`std::sort`，C++还有哪些值得关注的排序算法？

std::sort确实是万能药，但在某些特定场景下，标准库还提供了其他更专业的排序或部分排序算法，它们能提供更好的性能或满足特定的需求。

std::stable_sort：

用途： 当你的元素具有相同的“键”时，如果你希望这些相同键的元素的相对顺序在排序后保持不变，那么std::stable_sort就是你的选择。
例子： 假设你有一组学生，先按班级排序，然后你又想按分数排序。如果两个学生分数相同，你希望他们之前的相对顺序（比如在原始列表中谁在前面）仍然保持不变，std::stable_sort就能做到这一点。
性能： 通常比std::sort慢一些，因为它需要额外的空间来保证稳定性，复杂度通常是O(N log N)或O(N log^2 N)，但保证稳定性。

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

struct Person {
    std::string name;
    int age;
    int order; // 原始顺序

    void print() const {
        std::cout << "{" << name << ", " << age << ", order:" << order << "} ";
    }
};

int main() {
    std::vector<Person> people = {
        {"Alice", 30, 0},
        {"Bob", 25, 1},
        {"Charlie", 30, 2}, // Alice和Charlie年龄相同，Charlie在Alice之后
        {"David", 25, 3}    // Bob和David年龄相同，David在Bob之后
    };

    std::cout << "原始顺序: ";
    for (const auto& p : people) p.print();
    std::cout << std::endl;

    // 使用 std::sort 按年龄升序
    // std::sort 不保证相同元素的相对顺序
    std::vector<Person> sorted_people = people;
    std::sort(sorted_people.begin(), sorted_people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });
    std::cout << "std::sort (按年龄): ";
    for (const auto& p : sorted_people) p.print();
    std::cout << std::endl;
    // 结果可能是: {Bob, 25, order:1} {David, 25, order:3} {Alice, 30, order:0} {Charlie, 30, order:2}
    // 或者 {David, 25, order:3} {Bob, 25, order:1} ... 相对顺序可能改变

    // 使用 std::stable_sort 按年龄升序
    // std::stable_sort 保证相同元素的相对顺序
    std::vector<Person> stable_sorted_people = people;
    std::stable_sort(stable_sorted_people.begin(), stable_sorted_people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });
    std::cout << "std::stable_sort (按年龄): ";
    for (const auto& p : stable_sorted_people) p.print();
    std::cout << std::endl;
    // 结果一定是: {Bob, 25, order:1} {David, 25, order:3} {Alice, 30, order:0} {Charlie, 30, order:2}
    // Bob在David之前，Alice在Charlie之前，因为它们在原始列表中就是这个顺序。
    return 0;
}

登录后复制

std::partial_sort：

用途： 当你只需要知道vector中最小（或最大）的N个元素，并且它们需要被排序时，std::partial_sort非常有用。它会将N个最小的元素放在vector的前N个位置，并且这N个元素是排好序的，而剩下的元素则不保证顺序。
例子： 找出班级中分数最高的5名学生。
性能： 通常比完全排序快，因为不需要对整个范围进行排序，复杂度是O(N log K)，其中K是你想要排序的元素数量。

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

int main() {
    std::vector<int> data = {9, 1, 8, 2, 7, 3, 6, 4, 5};
    int k = 3; // 我们只想找到最小的3个元素并排序

    // partial_sort 将最小的 k 个元素排序并放到前面
    std::partial_sort(data.begin(), data.begin() + k, data.end());

    std::cout << "部分排序 (最小的" << k << "个): ";
    for (int x : data) {
        std::cout << x << " ";
    }
    std::cout << std::endl; // 输出: 1 2 3 9 7 8 6 4 5 (前3个是排序的，后面不保证)
    return 0;
}

登录后复制

std::nth_element：
- 用途： 这是最“懒惰”的排序算法之一。它不会对整个vector进行排序，甚至不会对部分vector进行排序。它只会将第N个元素（按照排序后的顺序）放到它最终应该在的位置上，并确保所有比它小的元素都在它左边，所有比它大的元素都在它右边。这对于寻找中位数、分位数或者快速定位某个“第K大/小”的元素非常高效。
- 例子： 快速找到一个数组的中位数。
- 性能： 平均时间复杂度是线性的O(N)，最坏情况下是O(N^2)，但通常非常快。
```
#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> data = {9, 1, 8, 2, 7, 3, 6, 4, 5};
    int n_th_index = 4; // 寻找第5小的元素 (索引为4)

    // nth_element 会把第 n_th_index 处的元素放到它最终排序后的位置上
    // 并且保证它左边的元素都比它小，右边的都比它大
    std::nth_element(data.begin(), data.begin() + n_th_index, data.end());

    std::cout << "nth_element (第" << n_th_index + 1 << "小): ";
    for (int x : data) {
        std::cout << x << " ";
    }
    std::cout << std::endl; // 输出: 3 1 2 4 5 9 6 7 8 (第5小是5，它在索引4，左右两边无序但大小符合)
    std::cout << "第" << n_th_index + 1 << "小的元素是: " << data[n_th_index] << std::endl; // 输出: 5
    return 0;
}
```
登录后复制
在我看来，std::nth_element是一个被低估的工具。它在需要快速找到某个特定排名元素而不需要完整排序时，能提供显著的性能优势。比如，在做一些数据分析时，计算中位数就特别适合用它。