C++ STL 算法 sort 的自定义排序规则

C++ STL 算法 sort 的自定义排序规则

在 C++ 的标准模板库（STL）中，sort 算法是一个非常实用的工具，用于对给定范围内的元素进行排序。默认情况下，sort 使用的是升序排序。然而，在实际编程中，我们常常需要根据特定的需求定义自己的排序规则。本文将深入探讨如何在 sort 算法中使用自定义排序规则。

1. sort 算法简介

sort 函数定义在 <algorithm> 头文件中，它有两个重载版本。最常用的版本接受两个迭代器，分别指向要排序范围的起始和结束位置（不包括结束位置的元素）。例如：

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

int main() {
    std::vector<int> numbers = {5, 3, 7, 1, 9};
    std::sort(numbers.begin(), numbers.end());

    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

上述代码将 numbers 向量中的元素按升序排序并输出。默认情况下，sort 使用的是快速排序算法的一种变体，平均时间复杂度为 $O(n \log n)$，其中 n 是要排序的元素个数。

2. 自定义排序函数

为了使用自定义排序规则，我们需要提供一个比较函数。这个比较函数应该接受两个参数，并返回一个布尔值，表示第一个参数是否应该排在第二个参数之前。

2.1 函数指针作为比较函数

我们可以定义一个普通函数，并将其指针作为 sort 的第三个参数传递。例如，假设我们要对整数按降序排序：

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

bool compareDescending(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> numbers = {5, 3, 7, 1, 9};
    std::sort(numbers.begin(), numbers.end(), compareDescending);

    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

在上述代码中，compareDescending 函数比较两个整数 a 和 b，如果 a 大于 b，则返回 true，表示 a 应该排在 b 之前，从而实现降序排序。

2.2 仿函数作为比较函数

仿函数（functor）是一种行为类似函数的对象，通过重载 () 运算符实现。使用仿函数的优点是可以在对象中存储状态，这在某些复杂的排序场景中非常有用。

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

class CompareDescending {
public:
    bool operator()(int a, int b) const {
        return a > b;
    }
};

int main() {
    std::vector<int> numbers = {5, 3, 7, 1, 9};
    std::sort(numbers.begin(), numbers.end(), CompareDescending());

    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

这里定义了 CompareDescending 类，重载了 () 运算符。在 sort 调用中，创建了 CompareDescending 的临时对象作为比较函数。

3. 自定义类型的排序

当对自定义类型进行排序时，自定义排序规则变得尤为重要。假设我们有一个表示点的结构体 Point，我们可能希望根据点到原点的距离进行排序。

3.1 结构体定义与距离计算

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

struct Point {
    int x;
    int y;

    double distanceFromOrigin() const {
        return std::sqrt(x * x + y * y);
    }
};

3.2 使用函数指针进行排序

bool compareByDistance(const Point& a, const Point& b) {
    return a.distanceFromOrigin() < b.distanceFromOrigin();
}

int main() {
    std::vector<Point> points = {
        {3, 4},
        {1, 1},
        {5, 0}
    };

    std::sort(points.begin(), points.end(), compareByDistance);

    for (const Point& point : points) {
        std::cout << "(" << point.x << ", " << point.y << ") ";
    }
    return 0;
}

在上述代码中，compareByDistance 函数比较两个 Point 对象到原点的距离，sort 函数根据这个规则对 points 向量进行排序。

3.3 使用仿函数进行排序

class CompareByDistance {
public:
    bool operator()(const Point& a, const Point& b) const {
        return a.distanceFromOrigin() < b.distanceFromOrigin();
    }
};

int main() {
    std::vector<Point> points = {
        {3, 4},
        {1, 1},
        {5, 0}
    };

    std::sort(points.begin(), points.end(), CompareByDistance());

    for (const Point& point : points) {
        std::cout << "(" << point.x << ", " << point.y << ") ";
    }
    return 0;
}

这里通过 CompareByDistance 仿函数实现了同样的排序功能。

4. 复杂自定义排序规则

有时候，我们的排序规则可能会更加复杂。例如，对于字符串，我们可能希望先按长度排序，如果长度相同，再按字典序排序。

4.1 字符串排序示例

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

bool compareStrings(const std::string& a, const std::string& b) {
    if (a.length() != b.length()) {
        return a.length() < b.length();
    } else {
        return a < b;
    }
}

int main() {
    std::vector<std::string> words = {
        "apple",
        "banana",
        "cherry",
        "date",
        "fig"
    };

    std::sort(words.begin(), words.end(), compareStrings);

    for (const std::string& word : words) {
        std::cout << word << " ";
    }
    return 0;
}

在 compareStrings 函数中，首先比较字符串的长度，如果长度不同，较短的字符串排在前面；如果长度相同，则按字典序排序。

4.2 结合多个条件的结构体排序

假设我们有一个 Student 结构体，包含姓名、年龄和成绩，我们希望先按成绩降序排序，如果成绩相同，再按年龄升序排序，如果年龄也相同，再按姓名字典序排序。

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

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

bool compareStudents(const Student& a, const Student& b) {
    if (a.score != b.score) {
        return a.score > b.score;
    } else if (a.age != b.age) {
        return a.age < b.age;
    } else {
        return a.name < b.name;
    }
}

int main() {
    std::vector<Student> students = {
        {"Alice", 20, 85},
        {"Bob", 19, 90},
        {"Charlie", 20, 85},
        {"David", 18, 95}
    };

    std::sort(students.begin(), students.end(), compareStudents);

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

在 compareStudents 函数中，通过多层条件判断实现了复杂的排序规则。

5. Lambda 表达式作为比较函数

C++11 引入了 lambda 表达式，使得定义简单的比较函数变得更加简洁。

5.1 整数降序排序

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

int main() {
    std::vector<int> numbers = {5, 3, 7, 1, 9};
    std::sort(numbers.begin(), numbers.end(), [](int a, int b) {
        return a > b;
    });

    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

这里使用 lambda 表达式 [](int a, int b) { return a > b; } 定义了降序比较函数。

5.2 自定义结构体排序

对于前面的 Student 结构体，我们也可以使用 lambda 表达式进行排序。

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

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

int main() {
    std::vector<Student> students = {
        {"Alice", 20, 85},
        {"Bob", 19, 90},
        {"Charlie", 20, 85},
        {"David", 18, 95}
    };

    std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) {
            return a.score > b.score;
        } else if (a.age != b.age) {
            return a.age < b.age;
        } else {
            return a.name < b.name;
        }
    });

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

通过 lambda 表达式，我们可以在 sort 调用的地方直接定义复杂的比较逻辑，使代码更加紧凑。

6. 稳定性与自定义排序

排序算法的稳定性是指相等元素在排序前后的相对顺序保持不变。sort 算法默认是不稳定的。然而，在某些情况下，稳定性非常重要。例如，在对具有相同成绩的学生进行排序时，如果我们希望保持他们原来的顺序，就需要使用稳定的排序算法。

stable_sort 函数也定义在 <algorithm> 头文件中，它保证了相等元素的相对顺序。使用自定义排序规则的方式与 sort 类似。

6.1 stable_sort 示例

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

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

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

int main() {
    std::vector<Student> students = {
        {"Alice", 20, 85},
        {"Bob", 19, 85},
        {"Charlie", 20, 90},
        {"David", 18, 90}
    };

    std::stable_sort(students.begin(), students.end(), compareStudents);

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

在上述代码中，stable_sort 保证了成绩相同的学生（如 Alice 和 Bob，Charlie 和 David）的相对顺序不变。

7. 性能考虑

虽然 sort 算法的平均时间复杂度为 $O(n \log n)$，但在实际应用中，性能还可能受到比较函数的复杂度影响。如果比较函数的时间复杂度较高，整个排序过程的性能也会受到影响。

例如，在比较自定义结构体时，如果比较函数涉及复杂的计算，如大量的数学运算或字符串操作，可能会导致排序性能下降。在这种情况下，我们可以考虑提前计算一些值并存储在结构体中，以简化比较函数。

另外，对于大规模数据的排序，stable_sort 虽然保证了稳定性，但通常比 sort 性能略低，因为它需要更多的空间来维护相等元素的顺序。因此，在选择排序算法时，需要根据数据特点和需求权衡稳定性和性能。

8. 总结与实践建议

通过自定义排序规则，我们可以让 sort 算法满足各种复杂的排序需求。无论是简单的升序、降序，还是涉及自定义类型和多条件的复杂排序，都可以通过函数指针、仿函数或 lambda 表达式来实现。

在实际编程中，建议根据具体情况选择合适的方式定义比较函数。如果比较函数逻辑简单，使用 lambda 表达式可以使代码更简洁；如果需要存储状态或复用比较逻辑，仿函数是一个不错的选择；而函数指针则是一种传统且通用的方式。

同时，要注意排序算法的稳定性和性能。对于需要保持相等元素相对顺序的场景，选择 stable_sort；对于性能要求较高且稳定性不重要的场景，sort 通常是更好的选择。

通过深入理解和熟练运用 sort 算法的自定义排序规则，我们能够更高效地处理各种数据排序任务，提升程序的灵活性和实用性。

希望本文对您理解和使用 C++ STL 中 sort 算法的自定义排序规则有所帮助。在实际编程中不断实践，您将能够更加熟练地运用这一强大的工具。