C++ 算法库：排序函数详解及示例

算法库是 C++ 标准库中的一个头文件，提供了一系列的函数，用于各种常见的算法操作，如排序、查找、合并、删除、替换等。这些函数都是使用模板实现的，可以适用于不同类型的数据结构。

算法库中的排序函数

算法库中包含的排序函数主要有：

sort 函数
- 原型：void sort (RandomAccessIterator first, RandomAccessIterator last);
- 功能：对 [first, last) 区间内的元素进行升序排序。
- 示例代码：
```
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
sort(arr, arr + 10); // 数组 arr 中的元素变为 {1, 1, 2, 3, 3, 4, 5, 5, 6, 9}
```

stable_sort 函数

原型：void stable_sort (RandomAccessIterator first, RandomAccessIterator last);
功能：对 [first, last) 区间内的元素进行升序排序，保证相等元素的相对位置不变。

示例代码：

struct Student {
    string name;
    int age;
};
bool cmp(Student a, Student b) {
    return a.age < b.age;
}
Student stu[] = {{"Tom", 18}, {"Jack", 20}, {"Lucy", 18}, {"Mary", 19}};
stable_sort(stu, stu + 4, cmp); // 结构体数组 stu 中的元素按照年龄升序排序，相同年龄的按照原来的顺序

partial_sort 函数
- 原型：void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
- 功能：对 [first, last) 区间内的元素进行部分排序，保证前 middle-first 个元素是整个序列中最小的 middle-first 个元素。
- 示例代码：
```
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
partial_sort(arr, arr + 5, arr + 10); // 数组 arr 中前 5 个元素变为 {1, 1, 2, 3, 3}，其余元素的顺序不确定
```
nth_element 函数
- 原型：void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
- 功能：对 [first, last) 区间内的元素进行部分排序，保证第 n 个元素是整个序列中第 n 个最小的元素，[first, nth) 区间内的元素小于等于第 n 个元素，(nth, last) 区间内的元素大于等于第 n 个元素。
- 示例代码：
```
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
nth_element(arr, arr + 5, arr + 10); // 数组 arr 中第 5 个元素为 3，[arr, arr+5) 区间内的元素小于等于 3，(arr+5, arr+10) 区间内的元素大于等于 3
```
inplace_merge 函数
- 原型：void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
- 功能：将 [first, middle) 和 [middle, last) 两个有序区间合并为一个有序区间。
- 示例代码：
```
int arr[] = {1, 3, 5, 2, 4, 6};
inplace_merge(arr, arr + 3, arr + 6); // 数组 arr 中的元素变为 {1, 2, 3, 4, 5, 6}
```
merge 函数
- 原型：OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
- 功能：将有序区间 [first1, last1) 和 [first2, last2) 合并为一个有序区间，结果存储在 [result, result + (last1 - first1) + (last2 - first2)) 区间内。
- 示例代码：
```
int arr1[] = {1, 3, 5};
int arr2[] = {2, 4, 6};
int res[6];
merge(arr1, arr1 + 3, arr2, arr2 + 3, res); // 数组 res 中的元素为 {1, 2, 3, 4, 5, 6}
```
make_heap 函数
- 原型：void make_heap (RandomAccessIterator first, RandomAccessIterator last);
- 功能：将 [first, last) 区间内的元素调整为一个堆。
- 示例代码：
```
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
make_heap(arr, arr + 10); // 数组 arr 中的元素变为 {9, 6, 4, 3, 5, 1, 2, 1, 5, 3}
```
push_heap 函数
- 原型：void push_heap (RandomAccessIterator first, RandomAccessIterator last);
- 功能：将新元素加入到已经是堆的 [first, last-1) 区间内，使其仍然保持堆的性质。
- 示例代码：
```
int arr[] = {9, 6, 4, 3, 5, 1, 2, 1, 5, 3};
push_heap(arr, arr + 10); // 数组 arr 中的元素变为 {9, 6, 4, 3, 5, 1, 2, 1, 5, 3}，并且仍然是一个堆
```
pop_heap 函数
- 原型：void pop_heap (RandomAccessIterator first, RandomAccessIterator last);
- 功能：将 [first, last) 区间内的堆的根节点移动到区间的最后一个位置，然后重新调整 [first, last-1) 区间内的元素，使其仍然保持堆的性质。
- 示例代码：
```
int arr[] = {9, 6, 4, 3, 5, 1, 2, 1, 5, 3};
pop_heap(arr, arr + 10); // 数组 arr 中的元素变为 {5, 6, 4, 3, 3, 1, 2, 1, 5, 9}，并且仍然是一个堆
```
sort_heap 函数
- 原型：void sort_heap (RandomAccessIterator first, RandomAccessIterator last);
- 功能：将 [first, last) 区间内的元素排序，使其成为一个有序序列。
- 示例代码：
```
int arr[] = {5, 6, 4, 3, 3, 1, 2, 1, 5, 9};
sort_heap(arr, arr + 10); // 数组 arr 中的元素变为 {1, 1, 2, 3, 3, 4, 5, 5, 6, 9}
```

总结

使用 algorithm 库中的排序函数可以大大简化我们的代码，提高开发效率。选择合适的排序函数可以根据具体的需求和数据结构进行选择。