C++排序算法详解：掌握std::sort与std::stable_sort的核心技巧

当你的C++程序需要对数据进行排序时，站在你面前的是两个强大的工具：一个高效但不保证顺序，一个稍慢但保持稳定。

在C++编程中，数据排序是一项基础但至关重要的操作。C++标准库在 <algorithm> 头文件中提供了多种排序函数，其中最常用的就是 std::sort 和 std::stable_sort。

这两个函数看似相似，但在性能特性和应用场景上有着本质区别。本文将深入解析这两个排序工具，帮助你根据具体需求做出明智选择。

核心差异一览

为了让你快速了解两个函数的主要区别，我整理了下面的对比表格：

特性	std::sort	std::stable_sort
稳定性	不稳定（不保证相等元素的原始顺序）	稳定（保持相等元素的原始相对顺序）
时间复杂度	平均和最坏情况均为 O(N·log(N))	有足够额外内存时 O(N·log(N))，否则 O(N·log²(N))
空间复杂度	通常为 O(log N)（递归栈）	通常需要 O(N) 额外内存
主要算法	内省排序（快速排序+堆排序+插入排序）	归并排序（有足够内存时）
性能特点	通常更快，内存使用更少	保持元素相对顺序，适用于多级排序
典型应用	基本排序需求，元素唯一或顺序无关	需要保持相等元素原始顺序的场景

std::sort：高效通用的排序工具

基本用法

std::sort 是C++中最常用的排序函数，它对给定区间内的元素进行排序，默认按升序排列。

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

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 默认升序排序
    std::sort(numbers.begin(), numbers.end());
    
    std::cout << "Sorted numbers: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    // 输出：1 2 3 4 5 6 7 8 9
    
    return 0;
}

自定义排序规则

std::sort 的强大之处在于它支持自定义比较函数，这使得它可以按照各种复杂规则进行排序：

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

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", 35},
        {"David", 28}
    };
    
    // 使用自定义比较函数
    std::sort(people.begin(), people.end(), compareByAge);
    
    // 使用lambda表达式（更简洁）
    std::sort(people.begin(), people.end(), 
              [](const Person& a, const Person& b) {
                  return a.name < b.name; // 按姓名排序
              });
    
    return 0;
}

算法实现与性能

std::sort 通常采用内省排序实现，这是一种混合排序算法：

1. 主要使用快速排序算法
2. 当递归深度过大时（可能遇到最坏情况），切换到堆排序
3. 当分区大小较小时，使用插入排序

这种实现保证了在最坏情况下的时间复杂度为 O(N·log(N))，避免了简单快速排序可能出现的 O(N²) 最坏情况。

std::stable_sort：保持顺序的稳定排序

什么是稳定排序？

稳定排序的核心特性是：相等元素的相对顺序在排序后保持不变。这个特性在某些场景下至关重要。

考虑以下示例：

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

struct Student {
    std::string name;
    int score;
    int id; // 入学编号
};

bool compareByScore(const Student& a, const Student& b) {
    return a.score < b.score;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 85, 1001},
        {"Bob", 85, 1002},  // 与Alice分数相同，但id不同
        {"Charlie", 90, 1003},
        {"David", 80, 1004}
    };
    
    // 使用std::stable_sort按分数排序
    std::stable_sort(students.begin(), students.end(), compareByScore);
    
    // 输出结果：David(80), Alice(85), Bob(85), Charlie(90)
    // 注意：Alice和Bob分数相同，排序后Alice仍在Bob前面（保持原始相对顺序）
    
    return 0;
}

实际应用场景

稳定排序在以下场景中特别有用：

1. 多级排序：先按一个条件排序，再按另一个条件排序

// 先按姓名排序
std::stable_sort(students.begin(), students.end(), 
                 [](const Student& a, const Student& b) {
                     return a.name < b.name;
                 });

// 再按分数排序（相同分数的学生将保持姓名顺序）
std::stable_sort(students.begin(), students.end(), 
                 [](const Student& a, const Student& b) {
                     return a.score < b.score;
                 });

2. 需要保持原始顺序的排序：如按整数部分排序浮点数，但保持小数部分相对顺序

std::vector<double> numbers = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32};

// 只按整数部分排序
std::stable_sort(numbers.begin(), numbers.end(),
                 [](double a, double b) {
                     return static_cast<int>(a) < static_cast<int>(b);
                 });
// 结果中，1.41和1.73的相对顺序保持不变

算法实现与性能考虑

std::stable_sort 在内存充足时通常使用归并排序，时间复杂度为 O(N·log(N))。但如果系统无法分配足够内存（等于待排序序列长度），它会退化为时间复杂度 O(N·log²(N)) 的原位算法。

这意味着 std::stable_sort 通常比 std::sort 需要更多内存，并且在内存受限时性能可能下降。

如何选择合适的排序函数

选择std::sort的情况

• 当元素值唯一或相等元素的顺序不重要时
• 当需要最大性能且内存有限时
• 对基本数据类型（int、float、string等）排序
• 当只需要单级排序时

选择std::stable_sort的情况

• 当需要多级排序（先按A条件排，再按B条件排）时
• 当必须保持相等元素的原始相对顺序时
• 当排序具有多个相等键的记录时（如数据库记录）
• 当实现某些特定算法（如后缀数组构造）时

性能对比示例

为了直观展示两者性能差异，我们可以考虑一个简单测试：

#include <algorithm>
#include <vector>
#include <chrono>
#include <iostream>
#include <random>

int main() {
    const int N = 1000000;
    std::vector<std::pair<int, int>> data(N);
    
    // 生成测试数据：第一个元素是0-100的随机数，第二个元素是顺序编号
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, 100);
    
    for (int i = 0; i < N; ++i) {
        data[i] = {dis(gen), i};
    }
    
    auto data1 = data;
    auto data2 = data;
    
    // 测试std::sort
    auto start = std::chrono::high_resolution_clock::now();
    std::sort(data1.begin(), data1.end(),
              [](const auto& a, const auto& b) {
                  return a.first < b.first;
              });
    auto end = std::chrono::high_resolution_clock::now();
    auto sort_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    // 测试std::stable_sort
    start = std::chrono::high_resolution_clock::now();
    std::stable_sort(data2.begin(), data2.end(),
                     [](const auto& a, const auto& b) {
                         return a.first < b.first;
                     });
    end = std::chrono::high_resolution_clock::now();
    auto stable_sort_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "std::sort time: " << sort_time.count() << "ms\n";
    std::cout << "std::stable_sort time: " << stable_sort_time.count() << "ms\n";
    
    // 检查稳定排序是否保持了相对顺序
    bool is_stable = true;
    for (int i = 1; i < N; ++i) {
        if (data2[i].first == data2[i-1].first && data2[i].second < data2[i-1].second) {
            is_stable = false;
            break;
        }
    }
    std::cout << "std::stable_sort maintained relative order: " 
              << (is_stable ? "YES" : "NO") << std::endl;
    
    return 0;
}

在实际测试中，std::sort 通常比 std::stable_sort 快 10-30%，但后者保证了稳定排序的特性。

高级技巧与注意事项

1. 对复杂结构进行多级排序

struct Employee {
    std::string department;
    std::string name;
    int salary;
    int years_of_service;
};

// 方法一：使用单个复杂比较函数
bool compareEmployee(const Employee& a, const Employee& b) {
    if (a.department != b.department)
        return a.department < b.department;
    if (a.salary != b.salary)
        return a.salary > b.salary; // 薪资降序
    if (a.years_of_service != b.years_of_service)
        return a.years_of_service > b.years_of_service;
    return a.name < b.name;
}

// 方法二：使用多次stable_sort（更灵活）
void sortEmployees(std::vector<Employee>& employees) {
    // 最后排序的键优先级最高
    std::stable_sort(employees.begin(), employees.end(),
                     [](const Employee& a, const Employee& b) {
                         return a.name < b.name;
                     });
    std::stable_sort(employees.begin(), employees.end(),
                     [](const Employee& a, const Employee& b) {
                         return a.years_of_service > b.years_of_service;
                     });
    std::stable_sort(employees.begin(), employees.end(),
                     [](const Employee& a, const Employee& b) {
                         return a.salary > b.salary;
                     });
    std::stable_sort(employees.begin(), employees.end(),
                     [](const Employee& a, const Employee& b) {
                         return a.department < b.department;
                     });
}

2. 排序检查与验证

C++还提供了 std::is_sorted 和 std::is_sorted_until 函数来检查序列是否已排序：

std::vector<int> data = {1, 3, 5, 2, 4, 6};

if (std::is_sorted(data.begin(), data.end())) {
    std::cout << "Data is sorted\n";
} else {
    auto it = std::is_sorted_until(data.begin(), data.end());
    std::cout << "Data is sorted until position: " 
              << std::distance(data.begin(), it) << std::endl;
}

总结

std::sort 和 std::stable_sort 都是C++标准库中强大的排序工具，各有其适用场景：

• 选择 std::sort 当性能是关键，且不需要保持相等元素的相对顺序时。它的内省排序实现在大多数情况下提供了优异的性能表现。

• 选择 std::stable_sort 当需要多级排序或必须保持相等元素的原始顺序时。虽然它可能稍慢且需要更多内存，但稳定性是许多算法和应用的基本要求。

理解这两个函数的内部机制和性能特点，能帮助你在实际编程中做出更合适的选择，写出更高效、更可靠的代码。

无论选择哪个函数，都请记住：在排序前清晰定义你的排序需求，特别是当处理复杂数据结构时。正确使用这些排序工具，将极大提升你的C++程序的效率和可维护性。