c++的sort函数

C++ 标准库中的 sort 函数是一个非常常用的函数，用来对序列进行排序。它位于头文件 <algorithm> 中。sort 函数使用了一种混合了快速排序、插入排序和堆排序的算法（通常是 introsort），在最坏情况下的时间复杂度为 O(n log n)，而最好的情况下是 O(n log n) 或 O(n)。

函数签名：

template< class RandomIt >
void sort( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

参数解释：

1. first 和 last：这两个参数是迭代器，表示要排序的范围。first 是序列的开始迭代器，last 是序列的结束迭代器，排序的范围为 [first, last)，注意 last 是不包含在排序范围内的。
   例如：sort(dp,dp+n) 、第一个参数就是从dp[0]开始，第二个参数表示到dp[n-1]结束，又例如 sort(dp+1,dp+7)、就是表示对从dp[1]开始 dp[6]结束的元素进行排序。
2. Compare（可选）：这是一个二元比较函数，定义排序规则。如果不提供该参数，默认是按升序排序（使用 < 运算符）。如果你想自定义排序规则，例如降序或基于某个属性排序，可以传入这个函数对象。

示例代码：

1. 基本使用（升序排序）

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

int main() {
    std::vector<int> nums = {4, 2, 8, 5, 7, 1};
    
    // 使用默认的升序排序
    std::sort(nums.begin(), nums.end());
    
    std::cout << "Sorted in ascending order: ";
    for (int n : nums) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出：

Sorted in ascending order: 1 2 4 5 7 8

2. 自定义比较函数（降序排序）

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

int main() {
    std::vector<int> nums = {4, 2, 8, 5, 7, 1};
    
    // 使用自定义的降序比较函数
    std::sort(nums.begin(), nums.end(), std::greater<int>());
    
    std::cout << "Sorted in descending order: ";
    for (int n : nums) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出：

Sorted in descending order: 8 7 5 4 2 1

自定义比较函数

你可以定义一个自己的比较函数来排序。例如，假设我们有一个自定义的结构体，并且想要基于某个字段进行排序：

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

struct Person {
    std::string name;
    int age;
};

// 自定义比较函数，按 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}};
    
    // 使用自定义比较函数排序
    std::sort(people.begin(), people.end(), compareByAge);
    
    std::cout << "Sorted by age: \n";
    for (const Person& person : people) {
        std::cout << person.name << ": " << person.age << "\n";
    }

    return 0;
}

输出：

Sorted by age: 
Bob: 25
Alice: 30
Charlie: 35

总结：

• C++ 的 sort 函数提供了灵活的排序功能，既可以使用默认的升序排序，也可以通过自定义比较函数实现各种自定义排序逻辑。
• sort 适用于随机访问迭代器，因此可以对 std::vector、std::array 等容器进行排序。
• 如果你需要保持元素之间的顺序不变（例如对于相同的元素），可以使用 stable_sort，它是稳定排序，能保持相同元素的原有顺序。