STL 中排序相关算法总结

sort

①．头文件

sort 算法定义在头文件 #include 中。

②．算法作用

sort 算法是基于快速排序实现的，默认对指定范围内的元素进行升序排列。

③．使用条件

使用 sort 进行排序到容器必须支持随机访问，默认使用 < 运算符进行比较，也可以提供自定义比较函数。

④．代码示例

vector<int> vec = { 6,4,3,1,2,9,5,7,8 };
cout << "原序列:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
  
sort(vec.begin(), vec.end());

cout << endl << "排序后:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
1
2
3
4
5
6
7
8

stable_sort

①．头文件

stable_sort 算法定义在头文件 #include 中。

②．算法作用

stable_sort 算法是基于归并排序实现的，默认对指定范围内的元素进行升序排列，并且可以保证相同元素的相对位置不变。

③．使用条件

使用 stable_sort 进行排序到容器必须支持随机访问，默认使用 < 运算符进行比较，也可以提供自定义比较函数。

④．代码示例

vector<int> vec = { 6,4,3,1,2,9,5,7,8 };
cout << "原序列:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
  
stable_sort(vec.begin(), vec.end());

cout << endl << "排序后:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
1
2
3
4
5
6
7
8

partial_sort

①．头文件

partial_sort 算法定义在头文件 #include 中。

②．算法作用

partial_sort 算法是部分排序，默认升序排列，即把最新的 n 个元素排到开头。

③．使用条件

使用 partial_sort 进行排序到容器必须支持随机访问，默认使用 < 运算符进行比较，也可以提供自定义比较函数。

④．代码示例

vector<int> vec = { 6,4,3,1,2,9,5,7,8 };
cout << "原序列:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
  
partial_sort(vec.begin(),vec.begin()+5, vec.end());

cout << endl << "排序后:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
1
2
3
4
5
6
7
8

T

partial_sort_copy

①．头文件

partial_sort_copy 算法定义在头文件 #include 中。

②．算法作用

partial_sort_copy 算法是部分排序后把结果拷贝到另外一个容器中，默认升序排列，即获取排序后到前 n 个元素。

③．使用条件

使用 partial_sort_copy 进行排序到容器必须支持随机访问，默认使用 < 运算符进行比较，也可以提供自定义比较函数。

④．代码示例

vector<int> vec = { 6,4,3,1,2,9,5,7,8 };
cout << "原序列:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
  
vector<int> vec2(5);
partial_sort_copy(vec.begin(), vec.end(),vec2.begin(),vec2.end());

cout << endl << "排序后:" << endl;
for_each(vec2.begin(), vec2.end(), [](int i) { cout << i << ","; });
1
2
3
4
5
6
7
8
9

nth_element

①．头文件

nth_element 算法定义在头文件 #include 中。

②．算法作用

nth_element 算法排序后得到的结果是，第 n 个位置前的元素都不大于 n 处的元素值，第 n 个位置后的元素值都不小于 n 处的元素值。

③．使用条件

使用 nth_element 进行排序到容器必须支持随机访问，默认使用 < 运算符进行比较，也可以提供自定义比较函数。

④．代码示例

vector<int> vec = { 3,4,1,2,5,9,6,7,8 };
cout << "原序列:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
    
nth_element(vec.begin(), vec.begin()+4, vec.end());

cout << endl << "排序后:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
1
2
3
4
5
6
7
8

partition

①．头文件

partition 算法定义在头文件 #include 中。

②．算法作用

nth_element 算法排序后得到的结果是，满足条件到元素排在不满足条件到元素前面。

③．使用条件

使用 partition 进行排序到容器必须支持随机访问，默认使用 < 运算符进行比较，也可以提供自定义比较函数。

④．代码示例

vector<int> vec = { 3,4,1,2,5,9,6,7,8 };
cout << "原序列:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
  
partition(vec.begin(), vec.end(), [&](int i) {return  i > 4; });

cout << endl << "排序后:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
1
2
3
4
5
6
7
8

random_shuffle

①．头文件

random_shuffle 算法定义在头文件 #include 中。

②．算法作用

random_shuffle 算法的作用是随机打乱原来序列的顺序，默认采用 rand 作为随机数生成器。

③．代码示例

srand(time(nullptr));
vector<int> vec = { 3,4,1,2,5,9,6,7,8 };
cout << "原序列:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
  
random_shuffle(vec.begin(), vec.end());

cout << endl << "排序后:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
1
2
3
4
5
6
7
8
9

shuffle

①．头文件

shuffle 算法定义在头文件 #include 中。

②．算法作用

shuffle 算法的作用是随机打乱原来序列的顺序，第三个参数是传入一个随机数生成器

③．代码示例

vector<int> vec = { 3,4,1,2,5,9,6,7,8 };
cout << "原序列:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
  
mt19937 gen(random_device{}());
shuffle(vec.begin(), vec.end(),gen);

cout << endl << "排序后:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
1
2
3
4
5
6
7
8
9

reverse

①．头文件

reverse 算法定义在头文件 #include 中。

②．算法作用

reverse 算法的作用是对指定范围的序列进行反转操作。

③．代码示例

vector<int> vec = { 3,4,1,2,5,9,6,7,8 };
cout << "原序列:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
  
reverse(vec.begin(), vec.end());

cout << endl << "排序后:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
1
2
3
4
5
6
7
8

rotate

①．头文件

rotate 算法定义在头文件 #include 中。

②．算法作用

rotate 算法的执行结果是把指定位置 n 开始的区间排列到序列前面。

③．代码示例

vector<int> vec = { 1,2,3,4,5,6,7,8,9 };
cout << "原序列:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
  
rotate(vec.begin(), vec.begin()+3, vec.end());

cout << endl << "排序后:" << endl;
for_each(vec.begin(), vec.end(), [](int i) { cout << i << ","; });
1
2
3
4
5
6
7
8