C++ 排序函数 sort(),qsort()的用法

在 C++ 中，sort() 和 qsort() 是两种常用的排序函数，分别属于 C++ 标准库和 C 标准库，适用于不同的场景。sort() 更现代且高效，qsort() 则更适合 C 风格代码或兼容旧代码。以下是对两者用法的详细讲解，包括语法、示例、性能对比及最佳实践。

---

一、sort() 函数

1. 概述

• 头文件：#include <algorithm>
• 命名空间：std
• 功能：基于内省排序（Introsort，结合快速排序、堆排序和插入排序），对指定范围的元素进行高效排序。
• 复杂度：
• 平均：O(n log n)
• 最坏：O(n log n)（内省排序避免了快速排序的 O(n²) 最坏情况）
• 特点：支持自定义比较规则，适用于随机访问容器（如数组、std::vector）。

2. 语法

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp = std::less<T>());

• 参数：
• first：排序范围的起始迭代器（包含）。
• last：排序范围的结束迭代器（不包含）。
• comp（可选）：比较函数，默认为升序（std::less<T>）。
• 返回值：无（直接修改原容器）。
• 迭代器要求：必须是随机访问迭代器（如数组、vector），不适用于 list 或 set。

3. 用法示例

（1）对数组升序排序

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n); // 默认升序

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "; // 输出：1 2 5 5 6 9
    }
    return 0;
}

（2）对 vector 降序排序

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {5, 2, 9, 1, 5, 6};

    sort(vec.begin(), vec.end(), greater<int>()); // 降序

    for (int x : vec) {
        cout << x << " "; // 输出：9 6 5 5 2 1
    }
    return 0;
}

（3）自定义比较函数

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {5, 2, 9, 1, 5, 6};

    sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; }); // 降序

    for (int x : vec) {
        cout << x << " "; // 输出：9 6 5 5 2 1
    }
    return 0;
}

（4）对结构体排序

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {{"张三", 25}, {"李四", 30}, {"王五", 20}};

    sort(people.begin(), people.end(), 
         [](const Person& a, const Person& b) { return a.age < b.age; }); // 按年龄升序

    for (const auto& p : people) {
        cout << p.name << " " << p.age << endl;
        // 输出：
        // 王五 20
        // 张三 25
        // 李四 30
    }
    return 0;
}

4. 注意事项

• 稳定性：sort() 不是稳定排序，相同元素的相对顺序可能改变。需稳定排序时使用 stable_sort()。
• 比较函数：必须满足严格弱序（即 < 关系），否则可能导致未定义行为。
• 适用容器：仅支持随机访问迭代器（如 vector、array），不适用于 list（需用 list::sort()）。

---

二、qsort() 函数

1. 概述

• 头文件：#include <cstdlib>
• 功能：C 标准库提供的快速排序函数，通过函数指针定义比较规则。
• 复杂度：
• 平均：O(n log n)
• 最坏：O(n²)（取决于实现，未优化最坏情况）
• 特点：适合 C 风格代码，类型不安全，使用 void* 处理数据。

2. 语法

void qsort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*));

• 参数：
• base：数组起始地址。
• num：数组元素个数。
• size：每个元素的大小（字节）。
• compar：比较函数，返回负数（a < b）、0（a == b）、正数（a > b）。
• 返回值：无（直接修改原数组）。

3. 用法示例

（1）对整数数组排序

#include <iostream>
#include <cstdlib>
using namespace std;

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b); // 升序
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    qsort(arr, n, sizeof(int), compare);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "; // 输出：1 2 5 5 6 9
    }
    return 0;
}

（2）对结构体数组排序

#include <iostream>
#include <cstdlib>
using namespace std;

struct Person {
    string name;
    int age;
};

int comparePerson(const void* a, const void* b) {
    return ((Person*)a)->age - ((Person*)b)->age; // 按年龄升序
}

int main() {
    Person people[] = {{"张三", 25}, {"李四", 30}, {"王五", 20}};
    int n = sizeof(people) / sizeof(people[0]);

    qsort(people, n, sizeof(Person), comparePerson);

    for (int i = 0; i < n; i++) {
        cout << people[i].name << " " << people[i].age << endl;
        // 输出：
        // 王五 20
        // 张三 25
        // 李四 30
    }
    return 0;
}

4. 注意事项

• 类型不安全：使用 void* 需手动类型转换，容易出错。
• 性能：通常比 sort() 慢，因函数指针调用和未优化最坏情况。
• 稳定性：非稳定排序。
• 适用场景：C 风格代码或需要兼容 C 的场景。

---

三、sort() 与 qsort() 对比

特性	sort()	qsort()
头文件	<algorithm>	<cstdlib>
语言风格	C++ 标准库，模板化	C 标准库，函数指针
性能	更高（内省排序，编译时优化）	稍慢（函数指针调用，未优化最坏情况）
类型安全	类型安全（模板）	类型不安全（void*）
灵活性	支持 lambda、函数对象、比较器	仅支持函数指针
稳定性	非稳定（可用 stable_sort()）	非稳定
适用容器	随机访问迭代器（数组、vector 等）	仅数组
现代性	C++ 首选，高效且灵活	适合 C 或旧代码

---

四、最佳实践

1. 优先选择 sort()：

• 性能优于 qsort()，支持现代 C++ 特性（如 lambda）。
• 除非需要兼容 C 代码，否则避免 qsort()。

1. 使用 lambda 表达式（C++11+）：

   sort(vec.begin(), vec.end(), [](int a, int b) { return a % 2 < b % 2; }); // 按奇偶排序

3. 定义比较器：

• 为复杂对象重载 < 或提供比较函数。

   struct Person {
       string name;
       int age;
       bool operator<(const Person& other) const { return age < other.age; }
   };
   sort(people.begin(), people.end());

4. 确保稳定性：

• 若需保持相同元素的相对顺序，使用 stable_sort()。

   stable_sort(vec.begin(), vec.end());

5. 性能优化：

• 优化比较函数，减少计算开销。
• 对于小型数据，sort() 和 qsort() 性能差异不大。

5. 错误检查：

• 确保比较函数满足严格弱序，避免未定义行为。
• 检查迭代器范围有效性。

---

五、总结

• sort()：C++ 标准库的首选排序函数，高效、类型安全，支持灵活的比较规则，适合现代 C++ 开发。
• qsort()：C 风格函数，适合简单数组或兼容旧代码，但性能和安全性较差。
• 选择建议：优先使用 sort()，结合 lambda 或自定义比较器实现复杂排序需求。

如果需要更复杂的示例（如多字段排序、性能测试）或特定场景的实现，请告诉我！