C++高级_STL常用的排序算法详解

常用的排序算法

merge();       合并两个有序序列，存放到另一个序列。重载版本使用自定义的比较。

sort();           以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作。

random_shuffle();          对指定范围内的元素随机调整次序。重载版本输入一个随机数产生操作。

reverse();     将指定范围内元素重新反序排序。

merge()函数

合并两个有序序列，存放到另一个序列中。

merage(begin1, end1, begin2, end2, begin3);

sort()函数

默认以升序的方式重新指定范围内元素。

如果想修改排序规则，可输入比较函数

sort(begin, end, 谓词);

random_shuffle()函数

对指定范围内的元素随机调整次序

random_shuffle(begin, end);

reverse()函数

反转指定范围内元素

reverse(begin, end);

下面是练习演示代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <list>
#include <string>
#include <string.h>

using namespace std;

void show(int &value)
{
	cout << value << " ";
}

void test_merge()
{
	// 1 要合并的容器 必须是 已经排序的
	// 2 目标容器 需要开辟空间
	vector<int> vec1;
	vector<int> vec2;

	list<int> lst;

	for (int i = 0; i < 10; i++) {
		vec1.push_back(rand() % 20);
		vec2.push_back(rand() % 30);
	}

	sort(vec1.begin(), vec1.end(), less<int>());
	sort(vec2.begin(), vec2.end(), less<int>());

	for_each(vec1.begin(), vec1.end(), show);
	cout << endl;

	for_each(vec2.begin(), vec2.end(), show);
	cout << endl;

	lst.resize(vec1.size() + vec2.size());
	merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), lst.begin());

	for_each(lst.begin(), lst.end(), show);
	cout << endl;
}

class Student
{
public:
	Student()
	{
		this->name = NULL;
		this->id = 0;
	}
	Student(char* name, int id)
	{
		int len = strlen(name) + 1;
		this->name = new char[len];
		strcpy(this->name, name);
		this->id = id;
	}

	Student(const Student & s)
	{
		int len = strlen(s.name) + 1;
		this->name = new char[len];
		strcpy(this->name, s.name);
		this->id = s.id;
	}

	Student & operator=(const Student & s)
	{
		if (this->name != NULL) {
			delete[] this->name;
			this->name = NULL;
			this->id = 0;
		}
		
		int len = strlen(s.name) + 1;
		this->name = new char[len];
		strcpy(this->name, s.name);
		this->id = s.id;
	
		return *this;
	}

	void display()
	{
		cout << "name " << this->name << ",  " << "id  " << this->id << endl;
	}

	~Student() {
		if (this->name != NULL) {
			delete[] this->name;
			name = NULL;
			this->id = 0;
		}
	}

	int getId()  
	{
		return id;
	}

private:
	char * name;
	int id;
};

class StudentCompare
{
public:
	bool operator()( Student & s1,  Student & s2)
	{
		if (s1.getId() < s2.getId()) {
			return true;
		}
		else {
			return false;
		}
	}
};

void showStudent(Student & s)
{
	s.display();
}

void test_sort()
{
	Student s1("zhang3", 1);
	Student s2("zhang4", 2);
	Student s3("zhang5", 3);
	Student s4("zhang6", 4);
	Student s5("zhang7", 5);

	vector<Student> vecS;

	vecS.push_back(s5);
	vecS.push_back(s4);
	vecS.push_back(s1);
	vecS.push_back(s3);
	vecS.push_back(s2);

	for (vector<Student>::iterator it = vecS.begin(); it != vecS.end(); it++) {
		(*it).display();
	}
	cout << endl;


	//StudentCompare comObj;
	//sort(vecS.begin(), vecS.end(), comObj);
	sort(vecS.begin(), vecS.end(), StudentCompare());
	//swap  s1 = s2 


	for_each(vecS.begin(), vecS.end(), showStudent);
	cout << endl;
	//for (vector<Student>::iterator it = vecS.begin(); it != vecS.end(); it++) {
	//	(*it).display();
	//}
	//cout << endl;

}

void test_random()
{
	vector<int> vec1;

	for (int i = 0; i < 10; i++) {
		vec1.push_back(rand() % 20);
	}

	sort(vec1.begin(), vec1.end());

	for_each(vec1.begin(), vec1.end(), show);
	cout << endl;

	//随机洗牌

	random_shuffle(vec1.begin(), vec1.end());

	for_each(vec1.begin(), vec1.end(), show);
	cout << endl;


	string str = "123456789";

	random_shuffle(str.begin(), str.end());
	cout << str << endl;

}

void test_reverse()
{
	vector<int> vec1;

	for (int i = 0; i < 10; i++) {
		vec1.push_back(rand() % 20);
	}

	sort(vec1.begin(), vec1.end());

	for_each(vec1.begin(), vec1.end(), show);
	cout << endl;

	reverse(vec1.begin(), vec1.end());

	for_each(vec1.begin(), vec1.end(), show);
	cout << endl;
}

int main(void)
{
	
	//test_merge();
	//test_sort();

	//test_random();
	test_reverse();
	return 0;
}