c++的sort函数

2024-09-09T21:52:00

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. firstlast:这两个参数是迭代器,表示要排序的范围。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::vectorstd::array 等容器进行排序。
  • 如果你需要保持元素之间的顺序不变(例如对于相同的元素),可以使用 stable_sort,它是稳定排序,能保持相同元素的原有顺序。
当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »