算法入门到进阶(二)——STL和基本的数据结构(sort函数和next_permutation函数)
文章目录
sort
STL的排序函数sort()是非常常用的函数之一,它的定义有以下两种:
- void sort(RandomAccessIterator first, RandomAccessIterator last);
- void sort(RandomAccessIterator first, RandomAccessIterator last,Compare comp);
返回值:无
复杂度 O(nlog2n).
注意,它的排序范围是[ first last),包括first,不包括last。
sort()的比较函数
排序是对比元素的大小。sort()可以用自定义的比较函数进行排序,也可以用系统的4种函数排序,即less() , greater() , less_equal() , greater_equal()。在默认情况下,程序员是按从小到大的顺序排序的,less()可以不写。
案例
实现一个简单的排序
源码
#include<iostream>
#include<vector> //vector容器头文件
#include<algorithm> //sort函数头文件
using namespace std;
bool my_less(int i, int j) {//自定义小于
return i < j;
}
bool my_greater(int i, int j) {//自定义大于
return i > j;
}
int main() {
vector<int>a = { 3,7,2,5,6,8,5,4 };//定义一个数组
sort(a.begin(), a.begin() + 4); //对前4个进行排序(从小到大)
for (int i = 0; i <a.size(); i++) {
cout << a[i] << " ";
}
cout << endl;
sort(a.begin(), a.end()); //从小到大输出(默认)
for (int i = 0; i < a.size(); i++) {
cout << a[i] << " ";
}
cout << endl;
sort(a.begin(), a.end(), less<int>()); //从小到大输出
for (int i = 0; i < a.size(); i++) {
cout << a[i] << " ";
}
cout << endl;
sort(a.begin(), a.end(), my_less);//自定义小于排序
for (int i = 0; i < a.size(); i++) {
cout << a[i] << " ";
}
cout << endl;
sort(a.begin(), a.end(), greater<int>());//从大到小输出
for (int i = 0; i < a.size(); i++) {
cout << a[i] << " ";
}
cout << endl;
sort(a.begin(), a.end(), my_greater);//自定义从大到小输出
for (int i = 0; i < a.size(); i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}
运行结果
分析
sort()还可以对结构变量进行排序
struct Student{
char name[256];
int score;
};
bool compare(struct Student *a,struct Student *b){ //按分数从大到小排序
return a->score>b->score;
}
...
vector<struct Student *>list; //定义list ,把学生信息存到list中
...
sort(list.begin(),list.end(),compare);//按分数排序
相关函数
stable_sort():当排序元素相等时,保留原来的顺序。在对结构体排序时,当结构体中的排序元素相等时,如果需要保留原序,可以使用stable_sort()。
partial_sort():局部排序。例如有10个数字,求最小的5个数。如果用sort(),需要先全部排序,再输出前5个;而用partail_sort()可以直接输出前5个。
next_permutation
STL提供求下一个排列组合的函数next_permutation()。例如3个字符a,b,c组成的序列,next_permutation()能按字典序返回6个组合,即abc,acb,bac,bca,cab,cba。
函数next_permutation()的定义形式有下面两种形式:
- bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
- bool next_permutation(BidirectionalIterator first, BidirectionalIterator last Compare comp);
返回值:如果没有下一个排列组合,返回false,否则返回true。每执行next_permutation()一次,就会把新的排列放在原来的空间里。
复杂度O(n)。
注意,它排列的范围是[first, last),包括first,不包括last。
在使用next_permutation()的时候,初始序列一般是一个字典序最小的序列,如果不是,可以用sort()排序,得到最小序列,然后再使用next_permutation(),例题见后面的博客
例题:Ignatius and the Princess II
给定n个数字,从1到n,要求输出第m小的序列
输入:数字n和m,1<=n<=1000,1<=m<=10000。
输出:输出第m小的序列。
思路
程序的思路是首先生成一个123…n的最小字典序列,即初始序列,然后用next_permutation()一个一个地生成下一个字典序更大的序列。
源码
#include<iostream>
#include<algorithm>
using namespace std;
int a[1001];
int main() {
int n, m;
cout << "n m:";
while (cin >> n >> m) {
for (int i = 1; i <= n; i++) {
a[i] = i;
}
int b = 1;
do {
if (b == n) {
break;
}
b++;
} while (next_permutation(a + 1, a + n + 1));
//输出的第一个是a[1],最后一个是a[n]
//输出第m大的字典序。
for (int i = 1; i < n; i++) {
cout << a[i] << " ";
}
cout << a[n] << endl;
}
return 0;
}
运行结果
分析
(实话实说,我没太明白这个算法,有懂得朋友,欢迎评论区交流)
与next_permutation()相关的函数如下:
- prev_permutation():求前一个排列组合。
- lexicographical_compare():字典比较。
总结
后面博客进入第三章,搜索技术
相关文章
- Twitter-Snowflake:自增ID算法
- Java实现算法竞赛入门经典例题-蚂蚁
- Java实现 蓝桥杯VIP 算法训练 暗恋
- 机器学习入门:K-近邻算法
- 算法入门
- (算法)扔棋子
- 【python cookbook】【数据结构与算法】20.将多个映射合并为单个映射
- 机器学习从入门到放弃之决策树算法
- python入门-分类和回归各种初级算法
- 美颜算法技术的入门基础原理概述
- 【冒泡排序】十大排序算法之冒泡排序
- 区间DP与贪心算法的联系(uav Cutting Sticks && poj Fence Repair(堆的手工实现))
- 2344. 使数组可以被整除的最少删除次数-快速排序加贪心算法
- 爬楼梯-c语言力扣最快算法
- 序列最小最优化算法
- 算法-动态规划 Dynamic Programming--从菜鸟到老鸟 背包问题
- 循环冗余校验(CRC)算法入门引导
- KMP算法入门
- Nebula入门学习——day4 nGQL中的图查询和其他算法
- OpenCV入门(三十一)快速学会OpenCV 30 K近邻算法
- OpenCV入门(二十七)快速学会OpenCV 26 SIFT算法
- Python ---- 算法入门(3)分治算法解决【汉诺塔】问题
- 推荐系统算法01:快速入门协同过滤算法
- C语言入门之程序的灵魂(算法)及数据类型