bilibiliC++85-88_STL- 常用算法_排序

朴灿烈づ我的快乐病毒、 2022-10-30 05:13 6阅读 0赞

### 5.3 常用排序算法 ###

**学习目标：**

*  掌握常用的排序算法

**算法简介：**

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

#### 5.3.1 sort ####

**功能描述：**

*  对容器内元素进行排序

**函数原型：**

*  `sort(iterator beg, iterator end, _Pred);`
    
    // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
    
    // beg 开始迭代器
    
    // end 结束迭代器
    
    // \_Pred 谓词

**示例：**

#include<iostream>
    using namespace std;
    #include <algorithm>
    #include <vector>
    
    void myPrint(int val)
    { 
    	cout << val << " ";
    }
    
    void test01() { 
    	vector<int> v;
    	v.push_back(10);
    	v.push_back(30);
    	v.push_back(50);
    	v.push_back(20);
    	v.push_back(40);
    
    	//sort默认从小到大排序
    	sort(v.begin(), v.end());
    	for_each(v.begin(), v.end(), myPrint);
    	cout << endl;
    
    	//从大到小排序
    	sort(v.begin(), v.end(), greater<int>());
    	for_each(v.begin(), v.end(), myPrint);
    	cout << endl;
    }
    
    int main() { 
    
    	test01();
    
    	system("pause");
    
    	return 0;
    }
    /* 10 20 30 40 50 50 40 30 20 10 请按任意键继续. . . */

**总结：** sort属于开发中最常用的算法之一，需熟练掌握

#### 5.3.2 random\_shuffle ####

**功能描述：**

*  洗牌 指定范围内的元素随机调整次序

**函数原型：**

*  `random_shuffle(iterator beg, iterator end);`
    
    // 指定范围内的元素随机调整次序
    
    // beg 开始迭代器
    
    // end 结束迭代器

**示例：**

#include<iostream>
    using namespace std;
    #include <algorithm>
    #include <vector>
    #include <ctime>
    
    class myPrint
    { 
    public:
    	void operator()(int val)
    	{ 
    		cout << val << " ";
    	}
    };
    
    void test01()
    { 
    	srand((unsigned int)time(NULL));
    	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() { 
    
    	test01();
    
    	system("pause");
    
    	return 0;
    }
    /* 0 1 2 3 4 5 6 7 8 9 0 5 3 6 1 8 4 9 7 2 请按任意键继续. . . */

**总结：** random\_shuffle洗牌算法比较实用，使用时记得加随机数种子

#### 5.3.3 merge ####

**功能描述：**

*  两个容器元素合并，并存储到另一容器中

**函数原型：**

*  `merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);`
    
    // 容器元素合并，并存储到另一容器中
    
    // 注意: 两个容器必须是**有序的**
    
    // beg1 容器1开始迭代器  
    // end1 容器1结束迭代器  
    // beg2 容器2开始迭代器  
    // end2 容器2结束迭代器  
    // dest 目标容器开始迭代器

**示例：**

#include<iostream>
    using namespace std;
    #include <algorithm>
    #include <vector>
    
    class myPrint
    { 
    public:
    	void operator()(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 + 1);
    	}
    
    	vector<int> vtarget;
    	//目标容器需要提前开辟空间
    	vtarget.resize(v1.size() + v2.size());
    	//合并 需要两个有序序列
    	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());
    	for_each(vtarget.begin(), vtarget.end(), myPrint());
    	cout << endl;
    }
    
    int main() { 
    
    	test01();
    
    	system("pause");
    
    	return 0;
    }
    /* 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 请按任意键继续. . . */

**总结：** merge合并的两个容器必须的有序序列

#### 5.3.4 reverse ####

**功能描述：**

*  将容器内元素进行反转

**函数原型：**

*  `reverse(iterator beg, iterator end);`
    
    // 反转指定范围的元素
    
    // beg 开始迭代器
    
    // end 结束迭代器

**示例：**

#include<iostream>
    using namespace std;
    #include <algorithm>
    #include <vector>
    
    class myPrint
    { 
    public:
    	void operator()(int val)
    	{ 
    		cout << val << " ";
    	}
    };
    
    void test01()
    { 
    	vector<int> v;
    	v.push_back(10);
    	v.push_back(30);
    	v.push_back(50);
    	v.push_back(20);
    	v.push_back(40);
    
    	cout << "反转前： " << endl;
    	for_each(v.begin(), v.end(), myPrint());
    	cout << endl;
    
    	cout << "反转后： " << endl;
    
    	reverse(v.begin(), v.end());
    	for_each(v.begin(), v.end(), myPrint());
    	cout << endl;
    }
    
    int main() { 
    
    	test01();
    
    	system("pause");
    
    	return 0;
    }
    /* 反转前： 10 30 50 20 40 反转后： 40 20 50 30 10 请按任意键继续. . . */

**总结：** reverse反转区间内元素，面试题可能涉及到