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

作者likuolei

在 C++ 中，sort() 和 qsort() 是两种常用的排序函数，分别适用于不同场景。sort() 是 C++ 标准库 <algorithm> 中的函数，功能强大且灵活；qsort() 是 C 标准库 <cstdlib> 中的函数，继承自 C 语言，适用于 C 风格代码。以下是对两者用法的详细讲解，包括语法、示例和比较。

一、sort() 函数

1. 概述

  • 头文件：#include <algorithm>
  • 命名空间：std
  • 功能：对指定范围内的元素进行快速排序（通常基于内省排序，结合快速排序、堆排序和插入排序）。
  • 复杂度：平均 O(n log n)，最坏 O(n log n)（内省排序优化）。

2. 基本语法

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  • 参数：
  • first：排序范围的起始迭代器（包含）。
  • last：排序范围的结束迭代器（不包含）。
  • comp（可选）：比较函数，定义排序规则，默认为升序（<）。
  • 返回值：无（直接修改原容器）。

3. 用法示例

（1）对数组排序（升序）

#include <iostream>
#include <algorithm>
#include <vector>
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;

bool customCompare(int a, int b) {
    return a > b; // 降序
}

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

    sort(vec.begin(), vec.end(), customCompare);

    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;
};

bool comparePerson(const Person& a, const Person& b) {
    return a.age < b.age; // 按年龄升序
}

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

    sort(people.begin(), people.end(), comparePerson);

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

4. 注意事项

  • 迭代器要求：sort() 要求随机访问迭代器，因此适用于数组、vector、deque 等，不适用于 list 或 set。
  • 稳定性：sort() 不是稳定排序，相同元素的相对顺序可能改变。若需稳定排序，使用 stable_sort()。
  • 比较函数：comp 必须定义严格弱序（严格小于关系），否则可能导致未定义行为。

二、qsort() 函数

1. 概述

  • 头文件：#include <cstdlib>
  • 功能：C 风格的快速排序函数，基于比较函数对数组排序。
  • 复杂度：平均 O(n log n)，但实现依赖具体标准库，可能不如 sort() 优化。
  • 特点：通过函数指针指定比较规则，适合 C 风格代码。

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. 注意事项

  • 类型不安全：qsort() 使用 void* 指针，需手动指定元素大小和类型转换，容易出错。
  • 性能：qsort() 通常比 sort() 慢，因为其比较函数通过指针调用，且未充分利用 C++ 模板优化。
  • 稳定性：qsort() 不是稳定排序。
  • 适用场景：适合 C 风格代码或需要兼容 C 的场景。

三、sort() 与 qsort() 的比较

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

四、最佳实践

  1. 优先选择 sort()：
  • sort() 性能更高、类型安全、支持现代 C++ 特性（如 lambda）。
  • 除非需要兼容 C 代码或特定场景，否则避免使用 qsort()。
  1. 使用 lambda 表达式（C++11 及以上）：
   sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });
  1. 处理复杂对象：
  • 为结构体定义比较运算符或使用自定义比较函数。
  • 示例：
    cpp struct Person { string name; int age; bool operator<(const Person& other) const { return age < other.age; } }; sort(people.begin(), people.end()); // 直接使用 operator<
  1. 注意稳定性：
  • 如果需要保持相同元素的相对顺序，使用 stable_sort()。
  1. 性能优化：
  • 尽量减少比较函数的开销。
  • 对于小型数据集，sort() 和 qsort() 性能差异不大。

五、总结

  • sort()：C++ 标准库的首选排序函数，性能优越、类型安全，支持灵活的比较规则，适合现代 C++ 开发。
  • qsort()：C 风格的排序函数，适合简单数组或兼容 C 代码的场景，但性能和安全性稍逊。
  • 选择建议：除非有特殊需求（如维护旧代码），优先使用 sort()，结合 lambda 表达式或自定义比较器实现复杂排序逻辑。

如果需要更具体的示例（如排序复杂数据结构）或性能测试代码，请告诉我！

类似文章

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注