c++入门必学库函数sort的基本用法

一、sort函数的基本介绍

sort()函数是C++ STL标准库提供的一种排序函数，能够对数组或容器进行排序。可以用于排序基本数据类型、结构体、对象等各种数据类型。其中，数组的排序时简单易行的，容器的排序则更加强大方便。

sort()的函数原型如下：

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

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

二、参数说明及注意事项

sort()函数的两种形式，其参数解释如下：

• random_access_iterator first——表示排序范围的首元素指针。
• random_access_iterator last——表示排序范围的尾元素的下一个元素的指针。
• Compare comp——指定排序规则谓词，可选。不指定规则时，默认按升序排列。

注意：

• sort()排序是基本的快排算法，最差时间复杂度为$O(n^2)$，但是平均时间复杂度为$O(nlog2n)$，效率较高。
• sort()排序属于原地排序，即排序过程中不会产生新的序列，因此不需要消耗额外的空间。
• RandomAccessIterator满足以下要求，表示该迭代器是可随机访问的。

// 随机访问迭代器
template<class Iterator>
class random_access_iterator{
public:
    typedef ptrdiff_t                                       difference_type;
    typedef typename iterator_traits<Iterator>::iterator_category  iterator_category;
    typedef typename iterator_traits<Iterator>::value_type         value_type;
    typedef typename iterator_traits<Iterator>::pointer            pointer;
    typedef typename iterator_traits<Iterator>::reference          reference;
    // ...
};

三、sort()函数的使用示例

1. 对数组进行排序

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {1,3,2,6,5,4};
    int num = sizeof(arr) / sizeof(arr[0]);
    sort(arr, arr + num);

    for (int i = 0; i < num; i++)
        cout << arr[i] << " ";

    return 0;
}

输出结果为：

1 2 3 4 5 6

2. 对容器进行排序

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

using namespace std;

struct Student
{
    int id;
    string name;
    int age;
};

bool compare(const Student& s1, const Student& s2)
{
    return s1.id < s2.id;
}

int main()
{
    vector<Student> students = {
        {1, "Alice", 20},
        {2, "Bob", 19},
        {3, "Cindy", 21}
    };

    sort(students.begin(), students.end(), compare);

    for (auto& s : students)
        cout << s.id << " " << s.name << " " << s.age << endl;

    return 0;
}

输出结果为：

1 Alice 20
2 Bob 19
3 Cindy 21

以上是使用sort()函数的两个示例，通过上面的例子，我们可以发现sort()函数的基本使用方法，了解了sort()函数的基本用法后，可以进一步学习其常用API，例如重载了构造函数的结构体和使用C++11中的lambda函数等。