STL常用算法之排序算法詳解

更新時(shí)間：2024年01月05日 10:18:22 作者：萬(wàn)里顧—程

這篇文章主要介紹了STL常用算法之排序算法詳解,STL提供了六大組件,彼此之間可以組合套用,這六大組件分別是:容器、算法、迭代器、仿函數(shù)、適配器、空間配置器,本文主要講算法中的排序算法,需要的朋友可以參考下

STL常用算法排序算法

1、sort()

sort()：對(duì)容器或普通數(shù)組中范圍內(nèi)的元素進(jìn)行排序，默認(rèn)進(jìn)行升序排序，也可以自定義排序規(guī)則。
sort() 函數(shù)只對(duì) array、vector、deque 這 3 個(gè)容器提供支持。
sort() 函數(shù)在對(duì)自定義的類(lèi)對(duì)象實(shí)現(xiàn)排序時(shí)，需要在該類(lèi)的內(nèi)部提供移動(dòng)構(gòu)造函數(shù)和移動(dòng)賦值運(yùn)算符。

函數(shù)原型：該函數(shù)有以下兩種語(yǔ)法格式

//對(duì) [beg, end) 區(qū)域內(nèi)的元素做默認(rèn)的升序排序
sort (iterator beg,iterator end);
//按照指定的 comp 排序規(guī)則，對(duì) [beg, end) 區(qū)域內(nèi)的元素進(jìn)行排序
sort (iterator beg,iterator end, Compare comp);

參數(shù)說(shuō)明：

beg 開(kāi)始迭代器
end 結(jié)束迭代器
comp 標(biāo)準(zhǔn)庫(kù)提供的排序規(guī)則（如 greater<T>）；或普通函數(shù)以及函數(shù)對(duì)象接收的自定義的排序規(guī)則

默認(rèn)排序和標(biāo)準(zhǔn)庫(kù)提供的排序

#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>

void myPrint(int val) {
	cout << val << " ";
}
void test01() {
	vector<int> v{1,4,5,3,2};
	//默認(rèn)升序排序
	sort(v.begin(), v.end());//1 2 3 4 5
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
	//從大到小排序，標(biāo)準(zhǔn)庫(kù)提供的排序規(guī)則
	sort(v.begin(), v.end(), greater<int>());//5 4 3 2 1
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
}
int main() {
	test01();
	system("pause");
	return 0;
}

自定義排序規(guī)則

#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>

void myPrint(int val) {
	cout << val << " ";
}
//以普通函數(shù)的方式實(shí)現(xiàn)自定義排序規(guī)則(升序)
bool mycomp(int i, int j) {
	return (i < j);
}
//以函數(shù)對(duì)象的方式實(shí)現(xiàn)自定義排序規(guī)則(升序)
class mycomp2 {
public:
	bool operator() (int i, int j) {
		return (i < j);
	}
};

void test01() {
	vector<int> v{ 32, 71, 12, 45, 26, 80, 53, 33 };
	
	sort(v.begin(), v.end(), mycomp);//12 26 32 33 45 53 71 80
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
	
	sort(v.begin(), v.end(), mycomp2());//12 26 32 33 45 53 71 80
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
}
int main() {
	test01();
	system("pause");
	return 0;
}

2、random_shuffle()

random_shuffle()：指定范圍內(nèi)的元素隨機(jī)調(diào)整次序

函數(shù)原型：

random_suffle(iterator beg,iterator end);

參數(shù)說(shuō)明：

beg 開(kāi)始迭代器
end 結(jié)束迭代器

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>

void myPrint(int val) {
	cout << val << " ";
}
void test01() {
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	//打亂順序前的遍歷
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
	//打亂順序后的遍歷
	random_shuffle(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
}
int main() {
	//加入隨機(jī)數(shù)種子，使每次程序啟動(dòng)的隨機(jī)數(shù)都不一樣
	srand((unsigned int)time(NULL));
	test01();
	system("pause");
	return 0;
}

在這里插入圖片描述

3、merge()

合并排序，merge() 函數(shù)用于將 2 個(gè)有序序列合并為 1 個(gè)有序容器，前提是這 2 個(gè)有序容器的排序規(guī)則相同（要么都是升序，要么都是降序）。并且最終借助該函數(shù)獲得的新有序容器，其排序規(guī)則也和這 2 個(gè)有序容器要相同。

函數(shù)原型：該函數(shù)有以下兩種格式

//默認(rèn)升序?yàn)榕判蛞?guī)則，[beg1, end1) 和 [beg2, end2) 指定區(qū)域內(nèi)的元素必須支持 < 小于運(yùn)算符
merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
//自定義的 comp 規(guī)則作為排序規(guī)則，[beg1, end1) 和 [beg2, end2) 指定區(qū)域內(nèi)的元素必須支持comp 排序規(guī)則內(nèi)的比較運(yùn)算符
merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest, Compare comp);

參數(shù)說(shuō)明：

beg1 容器1開(kāi)始迭代器
end1 容器1結(jié)束迭代器
beg2 容器2開(kāi)始迭代器
end2 容器2結(jié)束迭代器
dest 目標(biāo)容器開(kāi)始迭代器，為最終生成的新有序序列指定存儲(chǔ)位置
comp 用于自定義排序規(guī)則

默認(rèn)排序

void myPrint(int val) {
	cout << val << " ";
}
void test01() {
	//有序的容器
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
		v2.push_back(i * 2);
	}
	//新有序容器
	vector<int> v3;
	//一定要提前給容器分配空間
	v3.resize(v1.size() + v2.size());
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	//打印出來(lái)的還是個(gè)有序序列
	for_each(v3.begin(), v3.end(), myPrint);//0 0 1 2 2 3 4 4 5 6 6 7 8 8 9 10 12 14 16 18
	cout << endl;
}

自定義排序規(guī)則

void myPrint(int val) {
	cout << val << " ";
}

//以普通函數(shù)的方式實(shí)現(xiàn)自定義排序規(guī)則(降序)
bool mycomp(int i, int j) {
	return (i > j);
}
//以函數(shù)對(duì)象的方式實(shí)現(xiàn)自定義排序規(guī)則(降序)
class mycomp2 {
public:
	bool operator() (int i, int j) {
		return (i > j);
	}
};

void test01() {
	//有序的容器
	vector<int> v1;
	vector<int> v2;
	for (int i = 10; i > 0; i--) {
		v1.push_back(i);
		v2.push_back(i * 2);
	}
	//新有序容器
	vector<int> v3;
	//一定要提前給容器分配空間
	v3.resize(v1.size() + v2.size());

	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin(), mycomp);
	for_each(v3.begin(), v3.end(), myPrint);//20 18 16 14 12 10 10 9 8 8 7 6 6 5 4 4 3 2 2 1
	cout << endl;

	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin(), mycomp2());
	for_each(v3.begin(), v3.end(), myPrint);//20 18 16 14 12 10 10 9 8 8 7 6 6 5 4 4 3 2 2 1
	cout << endl;
}

4、reverse()

reverse()函數(shù)：將容器指定范圍內(nèi)的元素進(jìn)行反轉(zhuǎn)

函數(shù)原型：

reverse(iterator beg,iterator end);

參數(shù)說(shuō)明：

beg 開(kāi)始迭代器
end 結(jié)束迭代器

void myPrint(int val) {
	cout << val << " ";
}
void test01() {
	vector<int> v1;
	//有序的容器
	for (int i = 0; i < 10; i++) {
		v1.push_back(i);
	}
	reverse(v1.begin(), v1.end());
	for_each(v1.begin(), v1.end(), myPrint);//9 8 7 6 5 4 3 2 1 0
	cout << endl;
}

到此這篇關(guān)于STL常用算法之排序算法詳解的文章就介紹到這了,更多相關(guān)STL排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: