C++ STL函数和排序算法的快排以及归并排序详解

1. 什么是STL？

STL（Standard Template Library）是C++标准库中的一部分，它是由若干个模板类和函数构成的集合，提供了一些常用的数据结构和算法。

其中，数据结构包括vector（可变长数组）、list（双向链表）等，算法包括sort（排序）、find（查找）等。

2. STL快排算法详解

快排算法是一种基于“分治”思想的高效排序算法。在C++ STL中，sort函数采用快排算法来实现。

sort函数的函数原型如下：

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

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

其中，第一个版本是默认的排序算法（使用快排算法），第二个版本是可以自定义比较函数的排序算法。

示例：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v {3, 1, 4, 2, 5};
    sort(v.begin(), v.end());
    for (auto i: v) {
        cout << i << " ";
    }
    return 0;
}

输出结果为：

1 2 3 4 5 

在上面的示例中，vector容器中的元素按照递增的顺序进行了排序。

3. STL归并排序算法详解

归并排序算法也是一种常用的高效排序算法。在C++ STL中，用于实现归并排序的函数是stable_sort函数。

stable_sort函数的函数原型如下：

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

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

其中，第一个版本是默认的排序算法（使用归并排序算法），第二个版本是可以自定义比较函数的排序算法。

示例：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v {3, 1, 4, 2, 5};
    stable_sort(v.begin(), v.end());
    for (auto i: v) {
        cout << i << " ";
    }
    return 0;
}

输出结果为：

1 2 3 4 5 

在上面的示例中，vector容器中的元素也按照递增的顺序进行了排序。

4. 总结

本文主要介绍了C++ STL中的快排算法和归并排序算法，其中快排算法由sort函数实现，归并排序算法由stable_sort函数实现。

通过本文的介绍，我们可以了解到在C++ STL中，排序算法主要使用快排和归并排序这两种算法实现，而具体使用哪种算法则是C++ STL库根据输入数据的特点自行决定的，因此使用sort函数和stable_sort函数可以方便快捷地进行排序。

另外，C++ STL library中还有很多其他数据结构和算法，大家可以自行查阅相关资料深入学习。