关于stable_sort()和sort()的区别：
C++中sort和stable_sort的区别：
- sort是快速排序实现，因此是不稳定的；stable_sort是归并排序实现，因此是稳定的；
- 对于相等的元素sort可能改变顺序，stable_sort保证排序后相等的元素次序不变；
- 如果提供了比较函数，sort不要求比较函数的参数被限定为const，而stable_sort则要求参数被限定为const，否则编译不能通过。
你发现有sort和stable_sort，还有 partition 和stable_partition， 感到奇怪吧。其中的区别是，带有stable的函数可保证相等元素的原本相对次序在排序后保持不变。
这里需要弄清楚一个问题，这里的相等，是指你提供的函数表示两个元素相等，并不一定是一摸一样的元素。
例如，如果你写一个比较函数:
bool less_len(const string &str1, const string &str2) // 限定为const
{
return str1.length() < str2.length();
}
此时，"apples" 和 "winter" 就是相等的，如果在"apples" 出现在"winter"前面，用带stable的函数排序后，他们的次序一定不变，如果你使用的是不带"stable"的函数排序，那么排序完 后，"winter"有可能在"apples"的前面。
举例说明：
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool comp_as_int(double i, double j)
{
return (int(i)<int(j));
}
int main()
{
double mydoubles[] = { 3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58 };
vector<double> v;
vector<double>::iterator it;
v.assign(mydoubles, mydoubles + 8); // 分配空间并赋值给另外一个数组
cout << "use default comparison:" << endl;
stable_sort(v.begin(), v.end());
for (it = v.begin(); it != v.end(); it++)
cout << *it << " ";
cout << endl;
cout << "use selfdefined comparison function comp_as_int():" << endl;
v.assign(mydoubles, mydoubles + 8);
//stable sort 是稳定排序。
stable_sort(v.begin(), v.end(), comp_as_int);
for (it = v.begin(); it != v.end(); it++)
cout << *it << " ";
cout << endl;
cout << "use comparison function comp_as_int():" << endl;
v.assign(mydoubles, mydoubles + 8);
//sort是不稳定排序。
sort(v.begin(), v.end(), comp_as_int);
for (it = v.begin(); it != v.end(); it++)
cout << *it << " ";
cout << endl;
cout << "if it is not sorted with stable_sort(), the sequence of all elements between 1 and 2 will be set randomly..." << endl;
}
nth_element函数
我们就用最普通的用法寻找第k位置的元素。
函数用法为：nth_element(first，kth，end)。
first，last 第一个和最后一个迭代器，也可以直接用数组的位置。
kth，要定位的第k个元素，能对它进行随机访问.
将第k_th元素放到它该放的位置上，左边元素都小于等于它，右边元素都大于等于它.
例如：
vector<int> a(9);
for(int i = 0; i < 9; i++) a[i] = i+1;
random_shuffle(a.begin(),a.end()); //随机打乱
for(int i = 0; i < 9; i++) cout << a[i] << " ";//927316845
cout << endl;
nth_element(a.begin(),a.begin()+4,a.end());
cout << *(a.begin()+4) << endl; //5
for(int i = 0; i < 9; i++) cout << a[i] << " ";//213456897
cout << endl;
可以发现函数只是把kth的元素放在了正确位置，对其他元素并没有排序，所以可以利用这个函数快速定位第k个元素，当然，这个函数也支持你直接写比较函数。
那么为什么要选择这个函数呢，这就和复杂度有关了，nth_element的空间复杂度为O(1)，在数据量大的时候时间复杂度为O(n)，数据少的情况最坏为O(n^2)，因为函数原理是随机访问，但实际运用过程中，基本都会是O(n)的时间复杂度。所以说是非常迅速的。
大致原理:
在当前区间[L,R]上，找一个基准位置mid, 通过线性的扫描交换,使得[L,mid)的元素都比mid小，(mid,R]的元素都比mid大. 此时mid上的元素就是第mid小的,然后判断k在哪半边，继续递归处理
make_heap的用法
make_heap()生成堆，他有两个参数，也可以有三个参数，前两个参数是指向开始元素的迭代器和指向结束元素的下一个元素的迭代器。第三个参数是可选的，可以用伪函数less()和greater()来生成大顶堆和小顶堆，其中type为元素类型。如果只传入前两个参数，默认是生成大顶堆。
push_heap()是在堆的基础上进行数据的插入操作，参数与make_heap()相同，需要注意的是，只有make_heap（）和push_heap（）同为大顶堆或小顶堆，才能插入。
pop_heap()是在堆的基础上，弹出堆顶元素。这里需要注意的是，pop_heap()并没有删除元素，而是将堆顶元素和数组最后一个元素进行了替换，如果要删除这个元素，还需要对数组进行pop_back()操作。
若用make_heap(), pop_heap(), push_heap()，需要添加头文件 # include 。
用less ()和greater () 需要添加头文件 # include 。
# include <iostream>
# include <functional>
# include <vector>
# include <algorithm>
using namespace std;
void printVec(vector<int> nums)
{
for (int i = 0; i < nums.size(); ++i)
cout << nums[i] << " ";
cout << endl;
}
int main(void)
{
int nums_temp[] = {8, 3, 4, 8, 9, 2, 3, 4};
vector<int> nums(nums_temp, nums_temp + 8);
cout << "sorce nums: ";
printVec(nums);
cout << "(默认)make_heap: "; // 大顶堆
make_heap(nums.begin(), nums.end()); //9 8 4 8 3 2 3 4
printVec(nums);
cout << "(less)make_heap: ";
make_heap(nums.begin(), nums.end(), less<int> ());//9 8 4 8 3 2 3 4
printVec(nums);
cout << "(greater)make_heap: ";
make_heap(nums.begin(), nums.end(), greater<int> ());
printVec(nums);//2 3 3 4 8 4 9 8
cout << "此时，nums为小顶堆" << endl;;
cout << "push_back(3)" << endl;
nums.push_back(3);
cout << "忽略第三个参数，即为默认)push_heap: ";
push_heap(nums.begin(), nums.end());
printVec(nums); // 2 3 3 4 8 4 9 8 3
cout << "第三个参数为greater: ";
push_heap(nums.begin(), nums.end(), greater<int>());
printVec(nums); // 2 3 3 3 8 4 9 8 4
cout << "(做替换)pop_heap: ";
pop_heap(nums.begin(), nums.end());
printVec(nums);// 4 3 3 3 8 4 9 8 2
cout << "pop_back(): ";
nums.pop_back();
printVec(nums); // 4 3 3 3 8 4 9 8
}
C++ merge()函数
merge() 函数用于将 2 个有序序列合并为 1 个有序序列，前提是这 2 个有序序列的排序规则相同（要么都是升序，要么都是降序）。并且最终借助该函数获得的新有序序列，其排序规则也和这 2 个有序序列相同。
1. #include <iostream> // std::cout
2. #include <algorithm> // std::merge
3. #include <vector> // std::vector
4. using namespace std;
5. int main() {
6. //first 和 second 数组中各存有 1 个有序序列
7. int first[] = { 5,10,15,20,25 };
8. int second[] = { 7,17,27,37,47,57 };
9. //用于存储新的有序序列
10. vector<int> myvector(11);
11. //将 [first,first+5) 和 [second,second+6) 合并为 1 个有序序列，并存储到 myvector 容器中。
12. merge(first, first + 5, second, second + 6, myvector.begin());
13. //输出 myvector 容器中存储的元素
14. for (vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) {
15. cout << *it << ' ';
16. }
17. return 0;
18. }
输出
5 7 10 15 17 20 25 27 37 47 57
C++ inplace_merge()函数
和 merge() 函数一样，inplace_merge() 函数也要求 [first, middle) 和 [middle, last) 指定的这 2 个序列必须遵循相同的排序规则，且当采用第一种语法格式时，这 2 个序列中的元素必须支持 < 小于运算符；同样，当采用第二种语法格式时，这 2 个序列中的元素必须支持 comp 排序规则内部的比较运算符。不同之处在于，merge() 函数会将最终合并的有序序列存储在其它数组或容器中，而 inplace_merge() 函数则将最终合并的有序序列存储在 [first, last) 区域中。
1. #include <iostream> // std::cout
2. #include <algorithm> // std::merge
3. using namespace std;
4. int main() {
5. //该数组中存储有 2 个有序序列
6. int first[] = { 5,10,15,20,25,7,17,27,37,47,57 };
7. //将 [first,first+5) 和 [first+5,first+11) 合并为 1 个有序序列。
8. inplace_merge(first, first + 5,first +11);
10. for (int i = 0; i < 11; i++) {
11. cout << first[i] << " ";
12. }
13. return 0;
输出:
5 7 10 15 17 20 25 27 37 47 57
可以看到，first 数组中包含 2 个升序序列，借助 inplace_merge() 函数，实现了将这 2 个序列合并为 1 个升序序列，且新序列仍存储在 first 数组中。
标签：函数,STL,元素,merge,算法,序列,include,小结,first From： https://www.cnblogs.com/success-zh/p/16660972.htmlhttps://blog.csdn.net/earbao/article/details/54911878
https://www.cnblogs.com/oddcat/p/10313192.html
https://www.cnblogs.com/xenny/p/9424894.html
https://blog.csdn.net/linkfqy/article/details/74857216