C++STL之sort和二分查找

C++ STL学习笔记

这篇笔记是对慕课上郭炜老师的c++课程自己的总结，方便日后复习

• 要使用其中的算法，需要#include<algorithm>

1.sort函数（时间复杂度 0(n*log(n)) )

1. 从小到大排序
   对一个基本类型的数组如int型，double型等。

sort（数组名+n1,数组名+n2）;

如果n1=0，则 +n1 可以不写
如上是对数组中范围为**[n1,n2)**的元素从小到大排序，实际上数组中排序元素为n1到n2-1。

int a[]={15,4,3,9,7,2,6};
sort(a.a+7);//整个数组从小到大排序
sort(a,a+3);//结果{3，4，15，9，7，2，6}
sort(a+2,a+5);//结果{15，4，3，7，9，2，6}

2. 从大到小排序
   对一个基本类型为T的数组

sort(数组名+n1,数组名+n2，greater);

int a[]={15,4,3,9,7,2,6};
sort(a+1,a+4,greater<int>()); //结果{15,9,4,3,7,2,6};

3. 自定义规则

sort(数组名+n1，数组名+n2,排序规则结构名())；

排序规则结构定义方式：

struct 结构名
{
	bool operator()(const T & a1,const T & a2) const {    
	//此处写规则；
	//若a1 应该 在a2前面，则返回true，否则返回false。
	//const不要忘掉
	}
};

例子如下

#include <iostream>
#include <iostream>
#include <algorithm>
using namespace std;
struct Rule1 //按从大到小排序
{
	bool operator() ( const int & a1,const int & a2) const {
	return a1 > a2;
	}
};
struct Rule2 //按个位数从小到大排序
{
	bool operator() ( const int & a1,const int & a2) const {
	return a1%10 <a2%10;
	}
};

2.二分查找算法

对排好序的数组二分查找
binary_search二分查找
lower_bound二分查找下界
upper_bound二分查找上界

1. 对从小到大的数组进行二分查找binary_ search
   binary_ search (数组名+n1，数组名+n2 , 要查找的值) ;

2. 自定义规则
   binary search (数组名+n1，数组名+n2, 值, 排序规则结构名()) ;
   查找区间为下标范围为**[n1,n2)的元素，下标为n2的元素不在查找区间内在该区间内查找"等于"**值的元素，返回值为true(找到)或false(没找到)。查找时的排序规则，必须和排序时的规则一致!
   "等于"的含义: a等于b <=> "a必须在b前面"和"b必须在a前面”都不成立

   如sort(a , a+6, rule() );是按个位数从小到大排
   则binary_search(a ,a+6,8,rule() )查找到个位数为8的就返回true。

例子如下

int main() { 
int a[] = {3，7 ,12 ,21 ,45,98};
cout <<" result:"<< binary_ search(a,a+6,12) << endl ;//result：1
cout<< " result: "<< binary_ search(a,a+6, 77) << end1 ;//result: 0
}

1. lower_bound二分查找下界
   在对元素类型为T的从小到大排好序的基本类型的数组中进行查找。
   T * lower_ bound (数组名+n1,数组名+n2,值) ;
   返回指针 T * p *p是查找区间里下标最小的，大于等于"值"的元素。如果找不到，p指向下标为n2的元素

2. 自定义规则
   T * lower_ bound (数组名+n1,数组名+n2,值, 排序规则结构名()) ;
   *p是查找区间里下标最小的，按自定义排序规则，可以排在"值"后面的元素。如果找不到，p指向下标为n2的元素

3. upper_bound二分查找上界
   在元素类型为T的从小到大排好序的基本类型的数组中进行查找。
   T * upper_ bound(数组名+n1,数组名+n2,值) ;
   *p是查找区间里下标最小的，大于"值"的元素。如果找不到，p指向下标为n2的元素

4. 自定义规则
   T * upper_ bound(数组名+n1,数组名+n2,值, 排序规则结构名()) ;
   *p是查找区间里下标最小的，按自定义排序规则，必须排在""值"后面的元素。如果找不到，p指向下标为n2的元素

例子如下

int a[7]={3,5,5,7,12,21,98};
int * p1=lower_bound(a,a+7,5);
cout << *p1 << endl;//输出5，指针指向第一个5
int * p2=upper_bound(a,a+7,5);
cout << *p2 <<endl;//输出7，指针指向第二个5的后一个数7

时间2020/2/10 13:42