C++ sort ()排序详解

C++ `sort()` 排序详解（2025 版，超详细）

在 C++ 中，sort() 是标准模板库（STL）中 <algorithm> 头文件提供的强大排序函数，用于对容器（如 std::vector、std::array 或普通数组）中的元素进行高效排序。它基于快速排序的优化变体（内省排序，Introsort），平均时间复杂度为 O(n log n)，并支持自定义比较规则。本教程从基础到高级，详细讲解 sort() 的用法、原理、优化和实际场景，结合代码示例，适合初学者到进阶开发者。内容基于 C++20 标准（截至 2025 年 10 月），参考 C++ 标准文档和社区资源（如 CPPReference、CSDN、GeeksforGeeks）。

第一阶段：`sort()` 基础概念（初学者级别）

1.1 `sort()` 是什么？

定义：std::sort 是 STL 的通用排序函数，位于 <algorithm> 头文件，用于对指定范围的元素按升序或自定义顺序排序。
头文件：

  #include <algorithm>

基本语法：

  std::sort(first, last); // 默认升序
  std::sort(first, last, comp); // 自定义比较器

first：迭代器，指向排序范围的起始位置（包含）。
last：迭代器，指向排序范围的结束位置（不包含）。
comp（可选）：比较函数/仿函数，定义排序规则。
支持容器：
动态数组：std::vector、std::deque。
静态数组：std::array、C 风格数组。
其他：任何支持随机访问迭代器的容器（如 std::list 不支持，需用 list::sort()）。
默认行为：按升序（< 运算符）排序。

1.2 基本示例

升序排序：

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

int main() {
    std::vector<int> vec = {5, 2, 9, 1, 5, 6};
    std::sort(vec.begin(), vec.end()); // 升序排序

    for (int x : vec) {
        std::cout << x << " ";
    }
    return 0;
}

输出：

1 2 5 5 6 9

降序排序（使用标准比较器）：

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

int main() {
    std::vector<int> vec = {5, 2, 9, 1, 5, 6};
    std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降序

    for (int x : vec) {
        std::cout << x << " ";
    }
    return 0;
}

输出：

9 6 5 5 2 1

C 风格数组：

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::sort(arr, arr + n); // 升序

    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

输出：同 vector 升序。

第二阶段：`sort()` 原理与性能（中级）

2.1 排序算法：内省排序（Introsort）

算法：std::sort 使用 Introsort，结合以下算法：
快速排序（QuickSort）：平均 O(n log n)，但最坏 O(n²)。
堆排序（HeapSort）：当递归深度过高时切换，保证 O(n log n)。
插入排序（InsertionSort）：小范围（<10 元素）使用，优化性能。
为什么用 Introsort？
快速排序快但不稳定（最坏情况退化）。
堆排序稳定但慢。
Introsort 结合优点，动态切换。
时间复杂度：
平均/最优：O(n log n)。
最坏：O(n log n)（堆排序保证）。
空间复杂度：O(log n)（递归栈）。

2.2 比较器（comp）

默认：operator<（升序）。
自定义比较器：
函数指针：
cpp bool cmp(int a, int b) { return a > b; // 降序 } std::sort(vec.begin(), vec.end(), cmp);
Lambda 表达式（C++11+）：
cpp std::sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });
仿函数（Functor）：
cpp struct Compare { bool operator()(int a, int b) const { return a > b; } }; std::sort(vec.begin(), vec.end(), Compare());
要求：
比较器必须提供严格弱序（严格弱排序，irreflexive、transitive）。
即：comp(a, a) == false，且若 comp(a, b) 和 comp(b, c) 则 comp(a, c)。

2.3 稳定性

std::sort 不保证稳定性：相等元素可能改变相对顺序。
替代：用 std::stable_sort（稍慢，O(n log n)，空间 O(n)）。
示例（不稳定）：

  #include <iostream>
  #include <vector>
  #include <algorithm>
  struct Item { int value, id; };
  int main() {
      std::vector<Item> items = {{1, 1}, {1, 2}, {2, 3}};
      std::sort(items.begin(), items.end(), 
                [](const Item& a, const Item& b) { return a.value < b.value; });
      for (const auto& item : items) {
          std::cout << item.value << "," << item.id << " ";
      }
      return 0;
  }

输出（可能）：1,2 1,1 2,3（id=1,2 顺序可能颠倒）。

第三阶段：高级用法与优化（高级）

3.1 自定义复杂排序

场景：按结构体字段排序。

#include <iostream>
#include <vector>
#include <algorithm>
struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {{"Alice", 90}, {"Bob", 85}, {"Charlie", 90}};
    // 按 score 降序，score 相同按 name 升序
    std::sort(students.begin(), students.end(), 
              [](const Student& a, const Student& b) {
                  if (a.score != b.score) return a.score > b.score;
                  return a.name < b.name;
              });

    for (const auto& s : students) {
        std::cout << s.name << ": " << s.score << std::endl;
    }
    return 0;
}

输出：

Alice: 90
Charlie: 90
Bob: 85

3.2 部分排序

std::partial_sort：仅排序前 k 个元素。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> vec = {5, 2, 9, 1, 5, 6};
    std::partial_sort(vec.begin(), vec.begin() + 3, vec.end()); // 前 3 个升序
    for (int x : vec) {
        std::cout << x << " ";
    }
    return 0;
}

输出：1 2 5 9 6 5（前 3 个排序，后续未定）。

3.3 优化技巧

小数据集：少于 50 元素，std::sort 自动用插入排序，效率高。
大向量：确保 std::vector 预分配空间（reserve），避免重新分配。

  std::vector<int> vec;
  vec.reserve(1000000); // 预分配

并行排序（C++17+）：
使用 std::execution::par 加速大数组排序。

  #include <execution>
  std::sort(std::execution::par, vec.begin(), vec.end());

要求：编译器支持（如 GCC 9+，需 -ltbb）。
避免拷贝：用引用或指针排序复杂对象。

  std::sort(vec.begin(), vec.end(), 
            [](const auto& a, const auto& b) { return a < b; });

3.4 性能对比

算法	时间复杂度（平均）	稳定性	适用场景
`std::sort`	O(n log n)	不稳定	通用排序
`std::stable_sort`	O(n log n)	稳定	需保持相对顺序
`std::partial_sort`	O(n log k)	不稳定	前 k 个排序
手写 QuickSort	O(n log n)	不稳定	学习/特殊场景

测试性能：

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
int main() {
    std::vector<int> vec(1000000);
    std::generate(vec.begin(), vec.end(), std::rand);
    auto start = std::chrono::high_resolution_clock::now();
    std::sort(vec.begin(), vec.end());
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Sort time: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
              << " ms" << std::endl;
    return 0;
}

输出（示例，i7-12700）：~50ms（1M 元素）。

第四阶段：实际应用场景

4.1 场景 1：排序自定义对象

#include <iostream>
#include <vector>
#include <algorithm>
struct Point {
    int x, y;
};
int main() {
    std::vector<Point> points = {{1, 2}, {3, 1}, {2, 3}};
    std::sort(points.begin(), points.end(), 
              [](const Point& a, const Point& b) {
                  return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;
              });
    for (const auto& p : points) {
        std::cout << "(" << p.x << "," << p.y << ") ";
    }
    return 0;
}

输出：按到原点的距离排序。

4.2 场景 2：排序字符串

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<std::string> words = {"banana", "apple", "cherry"};
    std::sort(words.begin(), words.end()); // 字典序
    for (const auto& w : words) {
        std::cout << w << " ";
    }
    return 0;
}

输出：apple banana cherry

4.3 场景 3：稳定排序需求

#include <iostream>
#include <vector>
#include <algorithm>
struct Record {
    int score;
    std::string name;
};
int main() {
    std::vector<Record> records = {{90, "Alice"}, {90, "Bob"}, {85, "Charlie"}};
    std::stable_sort(records.begin(), records.end(), 
                     [](const Record& a, const Record& b) { return a.score > b.score; });
    for (const auto& r : records) {
        std::cout << r.score << ": " << r.name << std::endl;
    }
    return 0;
}

输出：

90: Alice
90: Bob
85: Charlie

第五阶段：常见问题与最佳实践

5.1 常见问题

问题	原因	解决方案
无效迭代器	对非随机访问迭代器（如 `std::list`）使用 `std::sort`	使用 `list::sort()` 或转换为 `vector`。
未定义行为	比较器错误（违反严格弱序）	确保 `comp(a, a) == false`。
性能瓶颈	复杂对象拷贝	在比较器中使用引用。
越界错误	无效迭代器范围	检查 `first` 和 `last` 边界。

5.2 最佳实践

优先使用 Lambda：一次性比较器用 Lambda 更简洁。
预分配容器：大数据集用 vector::reserve。
选择稳定性：需保持相对顺序时用 std::stable_sort。
测试边缘情况：空数组、单个元素、已排序、逆序。
并行执行 (C++17+)：大数据集在多核 CPU 上用 std::execution::par。

5.3 调试技巧

日志比较器：在 comp 中添加调试输出追踪问题。

  auto cmp = [](int a, int b) {
      std::cout << "比较 " << a << " 和 " << b << std::endl;
      return a < b;
  };

验证范围：使用 assert 或检查 first != last。
工具：用 GDB/Visual Studio 调试，Valgrind 性能分析。

第六阶段：资源与进阶学习

学习路径：
1 天：掌握基本 sort() 用法（vector、数组）。
2-3 天：练习自定义比较器（结构体、Lambda）。
1 周：探索 stable_sort、partial_sort、并行排序。
资源：
官方：CPPReference (std::sort，https://en.cppreference.com/w/cpp/algorithm/sort)。
英文：GeeksforGeeks (https://www.geeksforgeeks.org/sort-c-stl/)。
中文：CSDN (https://blog.csdn.net/weixin_43883374/article/details/106926058) – STL 算法讲解。
书籍：《Effective STL》（Scott Meyers），Item 31。
视频：YouTube “C++ STL Sort” by The Cherno。
工具：
编译器：GCC 14+、Clang 17+、MSVC 2022。
IDE：Visual Studio、CLion、VS Code (C++ 扩展)。

总结：std::sort 是 C++ 中高效、灵活的排序工具，利用 Introsort 实现 O(n log n) 性能，支持自定义比较器（Lambda、仿函数）和高级特性（部分排序、并行执行）。掌握 sort() 可高效处理实际数据场景。如果有具体问题（如比较器 bug），欢迎提供代码，我可进一步指导！