C++系列-STL容器中的排序算法

算法	描述
sort(beg, end)	默认升序排列元素,容器支持的迭代器类型必须为随机访问迭代器
sort(beg, end, pred)	使用谓词pred排列元素
stable_sort(beg, end)	与sort类似，保留相等元素的顺序关系
stable_sort(beg, end, pred)	使用谓词pred执行stable_sort
partial_sort(beg, mid, end)	使用谓词pred执行stable_sort
partial_sort(beg, mid, end, pred)	使用谓词pred执行stable_sort
nth_element(beg, nth, end)	对单个元素进行定位，序列中如果按照顺序排列的第n个元素的位置进行定位，默认前面的元素小于它，后面的元素大于它
nth_element(beg, nth, end, pred)	使用谓词pred执行nth_element

💢sort and stable_sort举例

👉 👉 👉
sort默认的排序方式是从小到大，可以使用谓词限定排序方式。
stable_sort能保留相等元素的顺序关系。

code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;class Person
{
public:Person(string name, int age) : m_name(name), m_age(age) {}string m_name;int m_age;
};void print_vector(vector<Person>& vec)
{for (vector<Person>::iterator it = vec.begin(); it != vec.end(); it++){cout << "name: " << it->m_name << ", age: " << it->m_age << endl;	// 返回第一个元素}
}class SortAge
{
public:bool operator()(const Person &p1, const Person &p2){return p1.m_age < p2.m_age;}
};void test01()
{int array1[6] = { 22, 44, 31, 6, 25, -70 };// 默认是从小到大排列sort(array1, array1 + sizeof(array1)/sizeof(array1[0]));for (int i_loop = 0; i_loop < sizeof(array1) / sizeof(array1[0]); i_loop++)cout << array1[i_loop] << " ";cout << endl;// 使用谓词，按照绝对值从大到小的顺序排列sort(array1, array1 + sizeof(array1) / sizeof(array1[0]), [](int val1, int val2) -> int {return abs(val1) > abs(val2);});for (int i_loop = 0; i_loop < sizeof(array1) / sizeof(array1[0]); i_loop++)cout << array1[i_loop] << " ";cout << endl;
}void test02()
{vector<Person>vec1;Person p1("Zhangsan", 7);Person p2("Lisi", 8);Person p3("Wangwu", 9);Person p4("Zhaoliu", 7);Person p5("Liuqi", 8);vec1.push_back(p1);	vec1.push_back(p2);	vec1.push_back(p3);	vec1.push_back(p4);	vec1.push_back(p5);	stable_sort(vec1.begin(), vec1.end(), SortAge());print_vector(vec1);
}
void main()
{test01();test02();system("pause");
}result:
-70 6 22 25 31 44
-70 44 31 25 22 6
name: Zhangsan, age: 7
name: Zhaoliu, age: 7
name: Lisi, age: 8
name: Liuqi, age: 8
name: Wangwu, age: 9

💢partial_sort举例

👉 👉 👉
partial_sort的原型，void partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last), 将[_First, _Last) 范围内最小（或最大）的 _Mid-_First个元素移动到 [_First, _Mid) 区域中，并对这部分元素做升序（或降序）排序，其余元素按照原顺序。

code:
#include <iostream>
#include <algorithm>
using namespace std;void print_array(int* array, int array_len)
{for (int i_loop = 0; i_loop < array_len; i_loop++){cout << array[i_loop] << " ";}cout << endl;
}void test01()
{int array1[7] = { 22, 44, 31, 6, 25, -70, -50 };// void partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last), // 将[_First, _Last) 范围内最小（或最大）的 _Mid-_First个元素移动到 [_First, _Mid) 区域中，并对这部分元素做升序（或降序）排序// 将数组中最小的4个数排序，放在前面，后面的数按原顺序partial_sort(array1, array1 + 3, array1 + sizeof(array1) / sizeof(array1[0]));print_array(array1, sizeof(array1) / sizeof(array1[0]));// partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred),把数组中的元素按照_Pred指定的方式排序前4个，// 其它元素按照原有顺序。partial_sort(array1, array1 + 4, array1 + sizeof(array1) / sizeof(array1[0]), greater<int>());print_array(array1, sizeof(array1) / sizeof(array1[0]));
}void main()
{test01();system("pause");
}result:
-70 -50 6 44 31 25 22
44 31 25 22 -70 -50 6

💢partial_sort_copy举例

👉 👉 👉
partial_sort_copy的原型，_RanIt partial_sort_copy(_InIt _First1, _InIt _Last1, _RanIt _First2, _RanIt _Last2)把[_First1,_Last1)的元素排列，复制到[_First2,_Last2)中，array1不改变

code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;void print_array(int* array, int array_len)
{for (int i_loop = 0; i_loop < array_len; i_loop++){cout << array[i_loop] << " ";}cout << endl;
}void print_vector(vector<int> &vec)
{for (auto it=vec.begin(); it != vec.end(); it++){cout << *it << " ";}cout << endl;
}void test01()
{int array1[8] = { 22, 44, 31, 6, 25, -70, -50, 35 };vector<int> vec1(5);// (_InIt _First1, _InIt _Last1, _RanIt _First2, _RanIt _Last2), 把[_First1,_Last1)的元素排列，// 复制到[_First2,_Last2)中,array1不改变partial_sort_copy(array1, array1 + 5, vec1.begin(), vec1.end());print_array(array1, sizeof(array1) / sizeof(array1[0]));print_vector(vec1);
}void main()
{test01();system("pause");
}result:
22 44 31 6 25 -70 -50 35
6 22 25 31 44

💢nth_element举例

👉 👉 👉
nth_element(beg，kth，end),将第kth元素放到它该放的位置上，左边元素都小于等于它，右边元素都大于等于它。
除了nth外，其余的不保证排序。

code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;void test01()
{vector<int> vec1(9);for (int i = 0; i < 9; i++)vec1[i] = i + 1;random_shuffle(vec1.begin(), vec1.end());for (int i = 0; i < 9; i++)cout << vec1[i] << " ";cout << endl;nth_element(vec1.begin(), vec1.begin() + 4, vec1.end());cout << *(vec1.begin() + 4) << endl;for (int i = 0; i < 9; i++)cout << vec1[i] << " ";cout << endl;
}void main()
{test01();system("pause");
}result:
9 2 7 3 1 6 8 4 5
5
1 2 3 4 5 6 7 8 9