C++ sort函数使用指南与性能优化-嵌云网-嵌入式AI开发资源站

C++ sort函数使用指南与性能优化

爬一手好线杆

1. C++ sort函数基础入门

sort函数是C++标准库中一个极为常用的算法，位于头文件中。它提供了对容器内元素进行排序的功能，默认情况下按照升序排列。对于C++开发者来说，掌握sort函数的使用是基本功中的基本功。

1.1 sort函数的基本用法

sort函数最基本的用法是对数组或vector进行排序。它的函数原型如下：

cpp复制template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

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

最简单的使用示例：

cpp复制#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> nums = {4, 2, 5, 3, 1};
    
    // 默认升序排序
    std::sort(nums.begin(), nums.end());
    
    for (int num : nums) {
        std::cout << num << " ";
    }
    // 输出：1 2 3 4 5
    return 0;
}

注意：sort函数要求迭代器必须是随机访问迭代器，这意味着它可以直接用于vector、deque和原生数组，但不能直接用于list、set等容器（它们有自己专门的sort成员函数）。

1.2 sort的时间复杂度与稳定性

sort函数在C++标准中保证的时间复杂度是O(N log N)，这使它成为非常高效的排序算法。不过需要注意的是，sort不是稳定排序，也就是说，相等的元素在排序后可能会改变相对顺序。如果需要稳定排序，可以使用stable_sort函数。

2. 自定义排序规则

sort函数的真正强大之处在于它支持自定义比较函数，这使得我们可以按照任意规则对元素进行排序。

2.1 使用函数对象（Functor）作为比较器

cpp复制#include <algorithm>
#include <vector>
#include <iostream>

// 自定义比较函数对象
struct Compare {
    bool operator()(int a, int b) const {
        return a > b; // 降序排列
    }
};

int main() {
    std::vector<int> nums = {4, 2, 5, 3, 1};
    
    // 使用函数对象进行降序排序
    std::sort(nums.begin(), nums.end(), Compare());
    
    for (int num : nums) {
        std::cout << num << " ";
    }
    // 输出：5 4 3 2 1
    return 0;
}

2.2 使用lambda表达式

C++11引入的lambda表达式让自定义排序更加简洁：

cpp复制#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> nums = {4, 2, 5, 3, 1};
    
    // 使用lambda表达式进行降序排序
    std::sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;
    });
    
    for (int num : nums) {
        std::cout << num << " ";
    }
    // 输出：5 4 3 2 1
    return 0;
}