STl中的排序算法详细解析

概述

在STL中，sort是一种常用的排序算法。sort算法旨在将元素从小到大排序，但也可以使用cmp函数指定排序方式。

算法实现

sort算法基于“快速排序”算法的实现。其基本思想是从待排序列中选取一定的数值作为划分元素（pivot），通过一趟排序将所有比该元素小的数放到它的左边，所有比该元素大的数放到它的右边，然后再对左右两个区间进行调用，重复执行以上过程，直至完成对整个序列的排序。

排序过程中，采用的是分治法的思想，即将序列分为两个子序列分别进行排序。为了能更好地满足分治法的要求，我们通常选择待排序列中的第一个或最后一个元素作为划分元素（pivot），并称之为主元（median of the 3）。

语法

sort函数的语法如下：

template <class RandomAccessIterator>
void sort(RandomAccessIterator begin, RandomAccessIterator end);

其参数为：
- begin：指向容器的第一个元素的迭代器。
- end：指向容器的最后一个元素的后一个位置的迭代器。

对于类似vector、array、string等容器而言，都具有迭代器的概念，因此以上语法同样适用于这些容器。

示例说明

示例一

对于普通数组的排序操作，示例代码如下：

#include <iostream>
#include <algorithm>

using namespace std;

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

    sort(arr, arr+n);

    cout << "排序后的数组序列: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

此处，我们利用sort算法对一个int数组进行排序，并将排序后的结果输出到控制台上。

示例二

对于自定义类型的排序操作，示例代码如下（以学生信息为例）：

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

using namespace std;

struct Student {
    string name;
    int score;
};

bool cmp(Student a, Student b)
{
    return a.score < b.score;
}

int main()
{
    vector<Student> v;
    v.push_back({"Alice", 90});
    v.push_back({"Bob", 80});
    v.push_back({"Cathy", 70});
    v.push_back({"David", 60});

    sort(v.begin(), v.end(), cmp);

    cout << "排序后的学生信息: " << endl;
    for (int i = 0; i < v.size(); i++)
        cout << v[i].name << " " << v[i].score << endl;

    return 0;
}

此处，我们利用sort算法对一个存储学生信息的vector进行排序，并将排序后的结果输出到控制台上。其中，我们通过cmp函数指定了排序方式为按成绩从小到大的顺序排序。