C++如何使用STL排序算法sort-C++-PHP中文网

std::sort基于Introsort实现，兼具快排的高效、堆排序的最坏情况保障和插入排序的小数据优势，平均时间复杂度为O(N log N)，适用于vector等支持随机访问迭代器的容器。通过提供自定义比较器（如lambda表达式或函数对象），可实现升序、降序及多级排序逻辑，广泛应用于数据预处理、算法竞赛和业务排序场景；使用时需注意避免对象拷贝、选择合适容器、简化比较逻辑，并遵循严格弱序原则以确保正确性，必要时可结合std::stable_sort保证相等元素的相对顺序。

c++如何使用stl排序算法sort

C++中，使用STL的

std::sort

登录后复制

函数进行排序是一种非常高效且灵活的手段，它能够对各种容器（只要提供随机访问迭代器）中的元素进行升序或降序排列，甚至能根据你自定义的规则来排序。这背后通常是Introsort的实现，结合了快速排序的平均高性能、堆排序的最坏情况保障以及插入排序在小规模数据上的优势，所以你几乎不用担心它的效率问题。

解决方案

要使用

std::sort

登录后复制

，你首先需要包含

<algorithm>

登录后复制

头文件。它的基本用法非常直接：传入两个迭代器，分别指向要排序范围的起始和结束（开区间，即不包含结束迭代器指向的元素）。

最常见的场景是升序排序，例如对一个

std::vector<int>

登录后复制

或C风格数组：

#include <iostream>
#include <vector>
#include <algorithm> // 包含 std::sort

int main() {
    // 对 std::vector 进行升序排序
    std::vector<int> numbers = {5, 2, 8, 1, 9, 3};
    std::sort(numbers.begin(), numbers.end());
    // 输出: 1 2 3 5 8 9
    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    // 对 C 风格数组进行升序排序
    int arr[] = {7, 4, 0, 6, 2};
    std::sort(arr, arr + 5); // arr + 5 是指向数组末尾之后一个元素的指针
    // 输出: 0 2 4 6 7
    for (int i = 0; i < 5; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

登录后复制

如果你需要降序排序，或者有更复杂的排序逻辑，

std::sort

登录后复制

提供了第三个参数：一个比较函数（或函数对象、lambda表达式）。这个比较函数接受两个参数，并返回一个

bool

登录后复制

值，表示第一个参数是否“小于”第二个参数。

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

例如，降序排序：

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // 包含 std::greater

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9, 3};

    // 使用 lambda 表达式进行降序排序
    std::sort(numbers.begin(), numbers.end(), [](int a, int b) {
        return a > b; // 如果 a 大于 b，则认为 a 在排序上“小于”b（即排在b前面）
    });
    // 输出: 9 8 5 3 2 1
    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    // 或者使用 std::greater<int>() 函数对象
    std::vector<int> moreNumbers = {10, 20, 5, 15};
    std::sort(moreNumbers.begin(), moreNumbers.end(), std::greater<int>());
    // 输出: 20 15 10 5
    for (int n : moreNumbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

登录后复制

对于自定义数据类型，比如一个结构体，你可以根据其成员变量来排序：

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

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

int main() {
    std::vector<Student> students = {
        {"Alice", 95, 101},
        {"Bob", 88, 103},
        {"Charlie", 95, 102},
        {"David", 72, 100}
    };

    // 按分数降序排序，如果分数相同，则按ID升序排序
    std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) {
            return a.score > b.score; // 分数高的排前面
        }
        return a.id < b.id; // 分数相同，ID小的排前面
    });

    for (const auto& s : students) {
        std::cout << "Name: " << s.name << ", Score: " << s.score << ", ID: " << s.id << std::endl;
    }
    /*
    输出:
    Name: Alice, Score: 95, ID: 101
    Name: Charlie, Score: 95, ID: 102
    Name: Bob, Score: 88, ID: 103
    Name: David, Score: 72, ID: 100
    */

    return 0;
}

登录后复制

std::sort与其他排序方式相比，有哪些独特的优势和应用场景？

说实话，

std::sort

登录后复制

在C++标准库里真的是一个非常“万金油”的工具，我个人觉得它的优势主要体现在几个方面，这让它几乎成了我的默认排序选择。

首先是效率。它的平均时间复杂度是O(N log N)，这在理论上已经是比较好的了。更关键的是，大多数STL实现都用了Introsort，这玩意儿很聪明，它会根据数据规模和特性，在快速排序、堆排序和插入排序之间切换。这意味着你既能享受到快排在平均情况下的极速，又能避免快排在最坏情况（比如数据已经几乎有序或逆序）下退化成O(N^2)的尴尬。而堆排序则保证了最坏情况下的O(N log N)性能，小数据量时插入排序又很高效。这种混合策略，在我看来，比你手动实现任何一种单一排序算法都要来得稳健和高效。

其次是通用性和易用性。它不挑容器，只要你的容器能提供随机访问迭代器（比如

std::vector

登录后复制

、

std::deque

登录后复制

、C风格数组），你就能直接扔给

std::sort

登录后复制

。这省去了我们很多写循环、管理指针的麻烦。接口简洁明了，

begin()

登录后复制

和

end()

登录后复制

一传，基本上就搞定了。对我这种追求开发效率的人来说，这种“拿来即用”的特性简直是福音。

再来是灵活性。通过自定义比较器，

std::sort

登录后复制

能适应几乎所有排序需求。无论是升序、降序，还是根据对象某个成员、多个成员的组合，甚至是一些非常奇葩的排序规则，你都可以通过一个lambda表达式或函数对象轻松搞定。这种自定义的能力，让它在面对复杂业务逻辑时也能游刃有余。

至于应用场景，那可就多了。

数据预处理：在进行数据分析、查找之前，先对数据进行排序，能大大提高后续操作的效率，比如二分查找。
算法竞赛：在算法竞赛中，时间就是生命，
```
std::sort
```
登录后复制
的效率和便捷性让它成为选手们的首选。
业务逻辑排序：比如你有一个用户列表，需要按注册时间排序，或者按活跃度排序，甚至按用户等级和经验值组合排序，
```
std::sort
```
登录后复制
都能轻松应对。
图形学或游戏开发：对场景中的对象按距离排序，以便进行渲染优化（例如，从后往前渲染半透明物体）。

当然，这里也要提一下

std::stable_sort

登录后复制

。如果你排序的元素有“相等”的情况，并且你希望这些相等元素的相对顺序在排序后保持不变，那么

std::stable_sort

登录后复制

就是你的朋友。

std::sort

登录后复制

不保证这一点，它可能会打乱相等元素的相对顺序。但通常来说，

std::stable_sort

登录后复制

的效率会略低于

std::sort

登录后复制

，因为它需要额外的处理来维持稳定性。所以，如果不需要稳定性，就用

std::sort

登录后复制

；如果需要，就考虑

std::stable_sort

登录后复制

。

在使用std::sort时，常见的性能陷阱和优化策略有哪些？

尽管

std::sort

登录后复制

已经足够优秀，但我在实际开发中还是遇到过一些坑，或者说，有些地方如果处理不好，它的性能优势就可能大打折扣。了解这些陷阱并掌握优化策略，能让你用得更顺手。

Pascal基础教程 Pascal入门必备基础教程 CHM版

无论做任何事情，都要有一定的方式方法与处理步骤。计算机程序设计比日常生活中的事务处理更具有严谨性、规范性、可行性。为了使计算机有效地解决某些问题，须将处理步骤编排好，用计算机语言组成“序列”，让计算机自动识别并执行这个用计算机语言组成的“序列”，完成预定的任务。将处理问题的步骤编排好，用计算机语言组成序列，也就是常说的编写程序。在Pascal语言中，执行每条语句都是由计算机完成相应的操作。编写Pascal程序，是利用Pasca

查看详情

常见的性能陷阱：

不必要的拷贝开销：当你对包含自定义对象（尤其是大型对象）的容器进行排序时，如果你的比较器（lambda或函数）参数没有使用
```
const &amp;amp;
```
登录后复制
，那么每次比较都可能导致对象的临时拷贝。想象一下，一个10万个元素的
```
std::vector<MyBigStruct>
```
登录后复制
，每次比较都拷贝两个
```
MyBigStruct
```
登录后复制
，这个拷贝量是巨大的，会严重拖慢速度。
选择错误的容器：
```
std::sort
```
登录后复制
要求其操作的迭代器必须是随机访问迭代器。这意味着它不能直接用于
```
std::list
```
登录后复制
这样的双向链表。如果你硬要对
```
std::list
```
登录后复制
使用
```
std::sort
```
登录后复制
，编译器会报错。如果非要排序
```
std::list
```
登录后复制
，你可能需要先将其元素复制到一个
```
std::vector
```
登录后复制
中，排序后再复制回去（如果需要保持链表结构），但这会引入额外的复制开销。
比较器逻辑过于复杂或低效：比较器函数会被频繁调用，如果它的内部逻辑很复杂，比如包含了IO操作、数据库查询或者其他耗时计算，那么整个排序过程就会变得异常缓慢。我见过有人在比较器里做字符串正则匹配的，那性能简直是灾难。
局部性原理不佳：虽然
```
std::vector
```
登录后复制
通常缓存友好，但如果你的自定义对象内部包含大量指针，指向分散在内存各处的数据，那么在比较这些对象时，可能会导致频繁的缓存失效，从而降低性能。

优化策略：

比较器参数使用
const &amp;
登录后复制
：这是最基本也是最重要的一点。始终确保你的比较器函数（无论是lambda、函数对象还是普通函数）的参数是

const &amp;amp;

登录后复制

类型，以避免不必要的对象拷贝。

// 错误示例 (可能导致拷贝)
// std::sort(vec.begin(), vec.end(), [](MyObject a, MyObject b) { return a.value < b.value; });
// 正确示例 (避免拷贝)
std::sort(vec.begin(), vec.end(), [](const MyObject& a, const MyObject& b) { return a.value < b.value; });

登录后复制

选择合适的容器：对于需要频繁排序的数据，
```
std::vector
```
登录后复制
几乎总是首选。它的数据在内存中是连续存储的，提供了随机访问迭代器，并且缓存友好，这些特性都非常利于
```
std::sort
```
登录后复制
发挥最佳性能。如果你的数据确实需要链表特性（比如频繁在中间插入/删除），但又需要排序，可以考虑在排序时将其转存到
```
std::vector
```
登录后复制
中。
简化比较器逻辑：确保你的比较器函数尽可能地简洁高效。避免在其中执行任何耗时操作。如果比较需要一些预计算的结果，尝试在排序前计算好并存储在对象中，或者作为比较器的捕获变量。
利用C++17的并行排序：对于非常大的数据集，如果你的编译器支持C++17的并行算法策略，可以考虑使用
```
std::sort(std::execution::par, begin, end, comparator);
```
登录后复制
。这会让
```
std::sort
```
登录后复制
尝试在多个线程上并行执行排序，从而显著缩短执行时间。当然，这会引入多线程的开销，对于小数据集可能适得其反，并且你需要确保你的比较器是线程安全的。
预分配内存：如果
```
std::vector
```
登录后复制
在排序过程中因为元素数量增加而需要重新分配内存，这会带来额外的开销。如果能预估
```
vector
```
登录后复制
的最终大小，提前使用
```
vector::reserve()
```
登录后复制
来分配内存，可以减少这种开销。

如何为自定义数据类型或复杂场景编写高效且正确的比较函数？

编写一个高效且正确的比较函数，是充分发挥

std::sort

登录后复制

威力的关键。这不仅仅是语法问题，更是对“严格弱序”（Strict Weak Ordering）这个核心概念的理解。

核心原则：严格弱序（Strict Weak Ordering）

任何用于

std::sort

登录后复制

的比较函数，都必须满足严格弱序的条件。听起来有点学术，但其实很好理解：

非自反性：
```
comp(a, a)
```
登录后复制
必须为
```
false
```
登录后复制
。一个元素不能“小于”它自己。
非对称性：如果
```
comp(a, b)
```
登录后复制
为
```
true
```
登录后复制
，那么
```
comp(b, a)
```
登录后复制
必须为
```
false
```
登录后复制
。如果a小于b，那么b就不能小于a。
传递性：如果
```
comp(a, b)
```
登录后复制
为
```
true
```
登录后复制
且
```
comp(b, c)
```
登录后复制
为
```
true
```
登录后复制
，那么
```
comp(a, c)
```
登录后复制
也必须为
```
true
```
登录后复制
。这是最直观的“小于”关系。
不可比性传递性：如果
```
a
```
登录后复制
和
```
b
```
登录后复制
是“等价”的（即
```
comp(a, b)
```
登录后复制
和
```
comp(b, a)
```
登录后复制
都为
```
false
```
登录后复制
），且
```
b
```
登录后复制
和
```
c
```
登录后复制
也是“等价”的，那么
```
a
```
登录后复制
和
```
c
```
登录后复制
也必须是“等价”的。这一点对于多级排序尤其重要。

如果你违反了这些规则，

std::sort

登录后复制

的行为将是未定义的，可能会导致崩溃、死循环或者得到一个错误的结果。

编写技巧：

优先使用Lambda表达式：在现代C++中，lambda表达式是编写比较函数的首选。它们简洁、可以直接在调用

std::sort

登录后复制

的地方定义，并且可以捕获外部变量（如果需要）。

struct Item {
    std::string name;
    int value;
    double weight;
};

std::vector<Item> items = { /* ... */ };
double threshold = 10.0; // 假设需要根据某个外部阈值进行排序

std::sort(items.begin(), items.end(), [threshold](const Item& a, const Item& b) {
    // 示例：先按 value 降序，如果 value 相同，再按 weight 升序，
    // 并且如果 weight 小于 threshold，则认为它“更小”
    if (a.value != b.value) {
        return a.value > b.value; // value 降序
    }
    // value 相同，考虑 weight
    if (a.weight < threshold && b.weight >= threshold) {
        return true; // a 的 weight 小于 threshold，b 不小于，a 优先
    }
    if (a.weight >= threshold && b.weight < threshold) {
        return false; // b 的 weight 小于 threshold，a 不小于，b 优先
    }
    return a.weight < b.weight; // 都小于或都不小于 threshold，按 weight 升序
});

登录后复制

这个例子稍微复杂一点，但它展示了lambda的强大之处，能够捕获

threshold

登录后复制

并实现多级、带有自定义逻辑的排序。

多级排序的链式比较：这是处理复杂排序逻辑的常用模式。当你需要根据多个条件进行排序时，通常会先比较第一个条件，如果相等，再比较第二个条件，以此类推。
```
// 假设 Student 结构体如前所述：name, score, id
std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    if (a.score != b.score) {
        return a.score > b.score; // 主排序键：分数降序
    }
    // 分数相同，进入次排序键：ID 升序
    return a.id < b.id;
});
```
登录后复制
这种模式是严格弱序的天然体现，因为它明确定义了当主键相等时，如何通过次键来区分元素。

使用函数对象（Functor）：当你的比较逻辑非常复杂，或者需要维护一些状态时，函数对象（即重载了

operator()

登录后复制

的类）会比lambda更清晰。

class CustomStudentComparator {
public:
    // 构造函数可以接受一些状态参数
    CustomStudentComparator(int min_score_priority = 0) : min_score_priority_(min_score_priority) {}

    bool operator()(const Student& a, const Student& b) const {
        // 示例：分数高于某个阈值的优先，然后按分数降序，最后按ID升序
        bool a_high_score = (a.score >= min_score_priority_);
        bool b_high_score = (b.score >= min_score_priority_);

        if (a_high_score != b_high_score) {
            return a_high_score; // 高分优先
        }
        if (a.score != b.score) {
            return a.score > b.score; // 分数降序
        }
        return a.id < b.id; // ID升序
    }
private:
    int min_score_priority_;
};

// 使用：
// std::sort(students.begin(), students.end(), CustomStudentComparator(90));

登录后复制

这种方式在需要将比较逻辑封装起来，或者需要在运行时

以上就是C++如何使用STL排序算法sort的详细内容，更多请关注php中文网其它相关文章！