32.STL算法库详解

1.前言

STL内容的最后就是我们的STL提供的强大算法函数了，这些算法所在头文件:

#include<algorithm>

2.排序函数

首先是最常用的排序函数:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int num[5] = { 4,1,6,7,0 };
	vector<int> v{ 5,1,3,8,7 };
	//默认升序
	sort(num, num + 5);
	sort(v.begin(), v.end());
}

即可以排序普通数组，也可以排序容器。

可以在第三个参数填入自定义排序规则（后续函数同理, 不再赘述）:

	vector<int> v{ 5,1,3,8,7 };

	sort(v.begin(), v.end(),std::greater<int>()); //使用标准库的排序规则

	//填入lambda表达式,或函数, 自定义排序规则, 该函数有两个参数, 参数类型为你要排序的元素类型, 返回前一个大于后一个为true,则为降序
	sort(v.begin(), v.end(), [](int a, int b) {
		return a > b;
		});

上面的sort函数，如果排序的数据中存在相同元素，它不能保证这些元素的相对顺序，所以可以采用stable_sort：

	vector<int> v{ 5,1,1,8,7 };
	stable_sort(v.begin(), v.end());

它能保证相同的元素，相对位置不变，即前面的元素，一定在其它相等元素的前面。

有时候我们仅仅只想要取出100万个数据中最大的十个数据，如果按上面全排的话，有点没必要了,所以就可以用partial_sort函数

	vector<int> v{ 5,1,3,8,7 };
	partial_sort(v.begin(), v.begin()+3,v.end()); //将最小的三个元素放在前三个位置,需要自定义规则的,填第4个参数

前两个参数决定了我们需要选取多少个元素，并且第1与第3参数决定了选取的范围。

但它会更改原数据，如果不想更改原有数据，可以使用partial_sort_copy：

	vector<int> v{ 5,1,3,8,7 };
	vector<int> result(3); //保存排序结果
	partial_sort_copy(v.begin(), v.end(), result.begin(), result.end());

最后两个参数为保存结果的迭代器范围，前两个迭代器则表示排序的数据范围，如果要自定义排序，则继续填第5个参数填入lambda表达式等等。

上面我们是想要得到前几大(或小)的元素，但有时我们只想要得到第几大的元素，那么就可以使用nth_element：

	vector<int> v{ 5,1,3,8,7 };
	nth_element(v.begin(), v.begin() + 2, v.end());

它的原理是将第二个参数减去第一个参数作为要求的第几大元素，并将结果移动到第二个迭代器所在位置。

有时我们可能需要判断一个容器中的数据是否已经是排序的状态:

	vector<int> v{ 5,1,3,8,7 };
	is_sorted(v.begin(), v.end()); //判断是否为升序排序, 是返回true.否返回false
	is_sorted_until(v.begin(), v.end()); //判断是否为升序排序, 是返回迭代器的end, 否则返回破坏该排序的第一个元素迭代器

有时我们可能还需要将两个已经排好序的合并:

	vector<int> v1{ 1,2,3};
	vector<int> v2{ 4,5,6};
	vector<int> v3(6);

	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3); //将合并排序的结果保存到最后一个参数

或者在同一个容器中:

	vector<int> v1{ 4,5,6,1,2,3};