[数据结构与算法]STL--排序算法

常用排序算法

• sort???????????????????????? // 对容器内元素进行排序
• random_shuffle????? // 洗牌， 指定范围内的元素随机调整顺序
• merge??????????????????? // 容器元素合并，并存储到另一个容器中
• reverse?????????????????? // 反转指定范围内的元素

1. sort

对容器内的元素进行排序

• sort(iterator? beg,? iterator? end,? _Pred);

• 对容器内的元素进行排序
• beg? 起始迭代器
• end? 结束迭代器
• _Pred? 谓词

	#include<iostream>
	using namespace std;
	#include<vector>
	#include<algorithm>
	#include<functional>  // 内建函数对象
	
	// 常用的排序算法
	// sort
	void my_print(vector<int>&v)
	{
		for(vector<int>::iterator it=v.begin();it!=v.end();it++)
		{
			cout<<*it<<" ";
		}
		cout<<endl;
	}
	void m_print(int val)
	{
		cout<<val<<" ";
	}
	int main()
	{
		vector<int> v;
		v.push_back(10);
		v.push_back(30);
		v.push_back(50);
		v.push_back(20);
		v.push_back(40);
	
		// 遍历函数
		my_print(v);
		// 利用sort进行升序排列
		sort(v.begin(),v.end());
		cout<<"sort默认升序排列"<<endl;
		my_print(v);
		// for_each函数
		cout<<"for_each方式输出"<<endl;
		for_each(v.begin(),v.end(),m_print);// 必须提供仿函数
		cout<<endl;
	
		// 降序排列
		cout<<"内建函数对象降序输出"<<endl;
		sort(v.begin(),v.end(),greater<int>());// 可以自己写一个仿函数进行比较
		my_print(v);
		
		return 0;
	}

?2. random_shuffle

洗牌，指定范围内的元素调整次序

• random_shuffle(iterator? beg,? iterator? end);

	#include<iostream>
	using namespace std;
	#include<vector>
	#include<algorithm>
	#include<functional>  // 内建函数对象
	#include<ctime>
	
	// 常用的排序算法
	// random_shuffle
	void my_print(vector<int>&v)
	{
		for(vector<int>::iterator it=v.begin();it!=v.end();it++)
		{
			cout<<*it<<" ";
		}
		cout<<endl;
	}
	void m_print(int val)
	{
		cout<<val<<" ";
	}
	int main()
	{
		// 在随机调整时也要包含随机数的种子
		srand((unsigned int)time(NULL));
		
		vector<int> v;
		for(int i=0;i<10;i++)
		{
			v.push_back(i);
		}
		my_print(v);
	
		// 利用洗牌的算法打乱原本的顺序
		cout<<"打乱后:"<<endl;
		random_shuffle(v.begin(),v.end());
		// 遍历函数
		my_print(v);
		// 利用sort进行升序排列
		cout<<"升序排列后："<<endl;
		sort(v.begin(),v.end());
		// for_each函数
		for_each(v.begin(),v.end(),m_print);
		cout<<endl;
	
		// 降序排列
		cout<<"降序排列后："<<endl;
		sort(v.begin(),v.end(),greater<int>());
		my_print(v);
		return 0;
	}

?3. merge

两个容器只能同时升序或者同时降序

两个容器元素合并

• merge(iterator? beg1,? iterator? end1,? iterator? beg2,? iterator? end2,? iterator? dest);

• ?容器元素合并，并存储到另一个容器中
• 注意：两个容器必须是有序的
• dest? 目标容器的起始迭代器

	#include<iostream>
	using namespace std;
	#include<vector>
	#include<algorithm>
	#include<functional>  // 内建函数对象
	
	// 常用的排序算法
	// merge
	void my_print(vector<int>&v)
	{
		for(vector<int>::iterator it=v.begin();it!=v.end();it++)
		{
			cout<<*it<<" ";
		}
		cout<<endl;
	}
	void m_print(int val)
	{
		cout<<val<<" ";
	}
	int main()
	{
	
		vector<int> v;
		for(int i=0;i<10;i++)
		{
			v.push_back(i);
		}
		my_print(v);
		
		vector<int> v1;
		for(int i=2;i<20;i++)
		{
			v1.push_back(i);
		}
		my_print(v1);
	
		// 目标容器
		vector<int>v_target;
		v_target.resize(v.size()+v1.size());// 要提前开辟空间
		// 将两个有序数列合并到一起还是一个有序数列
		merge(v.begin(),v.end(),v1.begin(),v1.end(),v_target.begin());
		my_print(v_target);
		return 0;
	}

?4.reverse

将容器中的元素反转

• reverse(iterator? beg,? iterator? end);

	#include<iostream>
	using namespace std;
	#include<vector>
	#include<algorithm>
	#include<functional>  // 内建函数对象
	
	// 常用的排序算法
	// reverse 将容器内元素反转
	void my_print(vector<int>&v)
	{
		for(vector<int>::iterator it=v.begin();it!=v.end();it++)
		{
			cout<<*it<<" ";
		}
		cout<<endl;
	}
	void m_print(int val)
	{
		cout<<val<<" ";
	}
	int main()
	{
	
		vector<int> v;
		for(int i=0;i<10;i++)
		{
			v.push_back(i);
		}
		cout<<"反转前"<<endl;
		my_print(v);
		cout<<"反转后"<<endl;
		reverse(v.begin(),v.end());  // 顺序反转
		my_print(v);
		return 0;
	}