算法入门逐类突破（双指针——附sort()函数的使用）

• sort()函数解释
• 双指针解题

1.Sort函数包含在头文件为#include《algorithm>的c++标准库中，是一个专门用来排序的高效的函数，我们在解决问题时可以方便快捷的排列顺序。
2.sort（）函数中有三个参数，（数组首地址；需要结束的地址；排列方式）
第三个排列方式可以不写，系统会默认为从小到大；

让我们来看一下真实的案例
1.如果我们想从大到小排序，可以不写第三个参数
eg：

#include
 
#include//sort()函数所需头文件 
 
using namespace std;
 
int main()
 
{
 
	 int a[10]={4,5,9,3,8,2,1,4,0,3};//初始化数组 
	 
	 for(int i=0;i<10;i++)
	 
	 	cout< 
运行结果
 
 
 
 
当然，如果我们不想排完整个数组，只想将前几位从大到小排序也是可以的，
 
 
eg：
 
#include
 
#include//sort()函数所需头文件 
 
using namespace std;
 
int main()
 
{
 
	 int a[10]={4,5,9,3,8,2,1,4,0,3};//初始化数组 
	 
	 for(int i=0;i<10;i++)
	 
	 	cout< 
运行结果·
 
 可以看出数组前五位从小到大排列了，而数组后五位不变
 
 
 
2.如果我们想从大到小排列就必须要使用sort()函数的第三个参数了
 
 
**Sortt函数的第三个参数可以用这样的语句告诉程序你所采用的排序原则
 
less<数据类型>()//从小到大排序
 
greater<数据类型>()//从大到小排序**
 eg：
 
#include
 
#include 
 
using namespace std;
 
int main()
 
{
 
	 int a[10]={4,5,9,3,8,2,1,4,0,3};//初始化数组 
	 
	 for(int i=0;i<10;i++)
	 
	 	cout<());//没有第三个参数，系统默认从小到大排序 
	 
	 for(int i=0;i<10;i++)
	 
	 {
	 	cout< 
运行结果
 
 我们就可以实现从大到小排序了
 
 
 
重点还是算法，sort()函数就略讲到这里，还有很多细节没有讲到，但可以应对我们这次的算法题了；
 
 
双指针解题 
双指针解题时有两种类型，今天我们主要用一种，两个指针相向扫描
 1.我们首先定义左直和右值，left,和right，letf向右扫描，right向左扫描
 当right 我i们来看一道例题
 
 
 
题目:第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
 返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
 
 
 
 
示例：输入：people = [3,5,3,4], limit = 5
 输出：4
 解释：4 艘船分别载 (3), (3), (4), (5)
 
 
题解;
 
class Solution {
public:
    int numRescueBoats(vector& people, int limit) {
        sort(people.begin(), people.end());//从小到大排序
 
        int num = 0;//返回的船数
        int min = 0;//左指针
        int max = people.size() - 1;//右指针
        while (min<=max) {
            if (people[min]+people[max]<=limit) {
                min++;
            }
            max--;
            num++;
        }
 
        return num;
    }
};
 
使用C语言实现略有不同，需要对排序方式进行定义
 
int cmp(const void *p1, const void *p2){
    return *(int*)p1 - *(int*)p2;
}
int numRescueBoats(int* people, int peopleSize, int limit)
{
    int num=0;
    int min=0;
    int max=peopleSize-1;
   qsort(people, peopleSize, sizeof(int), cmp);
    while(max>=min)
    {
        if(people[min]+people[max]<=limit)
        { 
            min++;
        }
        max--;
        num++;
    }
    return num;
}


 
这就是一种算法的技巧，利用相向的双指针解决问题