C++STL算法篇之排序和通用算法

2023-08-08 60

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： C++STL算法篇之排序和通用算法

使用算法的时候，包含的头文件

functional和algorithm

排序的准则：

默认的排序准则

1.less<类型>（）从小到大

greater<类型>（）从大到小

2.如果想要自定义排序的准则

可以通过仿函数，lambda表达式，函数适配器来实现**

sort排序

默认的是从小到大排序

#include<iostream>
#include<functional>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main()
{
  //1.sort排序
  vector<int> m = { 3,5, 6, 0, 1, 3, 7, 5, 3 };
  sort(m.begin(), m.end());
  sort(m.begin(), m.end(), less<int>()); //默认从小到大排序
  copy(m.begin(), m.end(), ostream_iterator<int>(cout, " ")); //流的方式打印数据
  cout << endl;
  sort(m.begin(), m.end(), greater<int>());
  copy(m.begin(), m.end(), ostream_iterator<int>(cout, " "));
  return 0;
}

注意：链表的排序不能使用sort算法，因为链表不是连续的，对于链表的排序可以调用内置的sort算法

stable_sort（保持相对顺序的排序）

使用lambda表达式和强制类型转换

以及copy函数打印

//2 stable_sort.
  //保持相对顺序的排序
  //一般使用double类型的数据
  vector<double> m1 = { 1.11, 5.23, 3.23, 7.89, 5.21, 9.99, 11.1, 2.22, 2.23 };
  stable_sort(m1.begin(), m1.end(), [](double a, double b) {return int(a) < int(b); }); //double类型用整形的类型来比较
  copy(m1.begin(), m1.end(), ostream_iterator<double>(cout, " "));

merge（归并排序）

不改变原容器的数据

有5个参数，实际上就是将2个有序的数组，合并成一个有序的数组，如果你会归并排序，那么就对此不陌生

前2个参数，表示第一个有序数组的范围

后面2个参数表示第二个有序数组的范围

最后一个参数表示数据打印的位置

//3.merge 归并排序
vector<int> m3 = { 1, 2, 4, 5, 0,4, 6, 7 };
  vector<int> result(m3.size());
  merge(m3.begin(), m3.begin() + 4, m3.begin() + 4, m3.end(), result.begin());
  copy(result.begin(), result.end(), ostream_iterator<int>(cout, " "));

inplace_merge(归并排序)

直接作用到原容器上面

//4.inplace_merge(直接作用到原容器上面)
  vector<int> m5 = { 1, 2, 4, 5, 0,4, 6, 7 };
  inplace_merge(m5.begin(), m5.begin() + 4, m5.end());
  copy(m5.begin(), m5.end(), ostream_iterator<int>(cout, " "));

nth_element(关键字排序)

实际上就理解成一种特殊的排序方式，结果其实跟归并排序貌似一样

//5.nth_element(关键字排序)
vector<int> m6 = { 1, 2, 4, 5, 0,4, 6, 7 };
  nth_element(m6.begin(), m6.begin() + 4, m6.end());
  copy(m6.begin(), m6.end(), ostream_iterator<int>(cout, " "));

partition

分类处理，按特定的条件把数据分为2组

/6.分类处理 partition
  vector<int> date = { 1, 3, 5, 7, 9, 0, 2, 4, 5 };
  partition(date.begin(), date.end(), [](int a) {return a< 6; });
  copy(date.begin(), date.end(), ostream_iterator<int>(cout, " ")); 
  //小于6的放到左边，大于6的放到右边

stable_partition

保持数据相对顺序，分类处理

一般是浮点数

//7.保持数据的相对稳定 一般用于浮点数
  //stable_partition
  vector<double> date1 = { 1.2, 0.3, 0.1, 2.4, 1.9, 6.9, 4.5 };
  stable_partition(date1.begin(), date1.end(), [](double a) {return int(a) < 2; });
  copy(date1.begin(), date1.end(),ostream_iterator<double>(cout, " "));

partial_sort(局部排序)

partial_sort_copy

局部排序的结果放到新的容器里

//9.局部排序结果另存 partial_sort_copy
  vector<int> mmm1 = { 1, 4, 4, 3, 2 };
  vector<int> result1(2);
  partial_sort_copy(mmm1.begin(), mmm1.begin() + 2, result1.begin(), result1.end());
  copy(result1.begin(), result1.end(), ostream_iterator<int>(cout, " "));

random_shuffle

乱序算法

注意：这里乱序算法一般搭配随机数种子使用，不然的话，每次出现的结果是一样的

//10.乱序算法 random_shuffle
  //随机数种子
  srand((unsigned)time(nullptr));
  vector<int> mmm2 = { 1, 2 ,3, 4, 5, 6, 7, 8, 9 };
  random_shuffle(mmm2.begin(), mmm2.end());
  copy(mmm2.begin(), mmm2.end(), ostream_iterator<int>(cout, " "));

reverse（逆置）

//11.逆置 reserve
  string str1 = "I love you";
  reverse(str1.begin(), str1.end());
  cout << str1 << endl;

reverse_copy( 逆置另存)

注意:另存的容器都要定义大小，刚定义是没有空间，不然就会出现越界问题

//12.逆置另存  reverse_copy
  string str2 = "ABCDEFG";
  string str3;
  str3.resize(77); //创建空间大
  reverse_copy(str2.begin(), str2.end(), str3.begin());
  cout << str3 << endl;

rotate(移动元素到末尾)

//13.移动元素到末尾 rotate
  string str4 = "ABCDEF";
  rotate(str4.begin(), str4.begin() + 2, str4.end());
  cout << str4 << endl;
  //将前2个元素 移到末尾

rotate_copy

移动元素到末尾结果另存

//14.移动元素到末尾另存 rotate_copy
  string str5 = "ABCDEFGHIJK";
  string str6;
  str6.resize(str5.size());
  rotate_copy(str5.begin(), str5.begin() + 4, str5.end(), str6.begin());
  cout << str6 << endl;