[C++知识库]2021.1.9——1.10

上午：
【1】听网课（回溯）
【2】洛谷：自然数的拆分（套用模板做的）

下午：
听学长讲课（讲的挺好）；
【１】讲了深搜和广搜。（只是感觉听完之后更加的混乱了）
（＝＝！）
深搜是基于递归，广搜依靠队列；

【２】快排的代码实现（两种方法）：

//这是让课后自己了解的填坑法：
#include<stdio.h>
void fastsort(int *a,int left,int right)
{
    int key=a[left];
    int first=left,last=right;
    //一定一定不要忘了结束条件（我就傻不拉几的忘记了）
    if(left>right)
        return;
    while(first<last)
    {
        while(first<last&&a[last]>key)
        {
            last--;
        }
        if(first<last)
        {
            a[first]=a[last];
            first++;
        }
        while(first<last&&a[first]<key)
        {
            first++;
        }
        if(first<last)
        {
            a[last]=a[first];
            last--;
        }
    }
    a[first]=key;
    //printf("%d\n",key);
    fastsort(a,left,last-1);
    fastsort(a,first+1,right);
}
int main()
{
    int a[11];
    int n;
    int left=0,right=9;
    for(int i=0;i<10;i++)
    {
        scanf("%d",&a[i]);
    }
    fastsort(a,left,right);
    for(int i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}
//其实最重要的是原理，知道了原理以后代码就好写了

//这是不知道什么法（和那个啊哈算法上是一个亚子的）：
#include<stdio.h>
void fastsort(int *a,int left,int right)
{
    int key=a[left];
    int l=left,r=right;
    if(left>right)
        return;
    while(l<r)
    {
       while(l<r&&a[r]>=key)
       {
           r--;
       }
       while(l<r&&a[l]<=key)
       {
           l++;
       }
       if(l<r)
       {
           int temp=a[r];
           a[r]=a[l];
           a[l]=temp;
       }
    }
    //下面几行操作是将基准点给移到它该处于的位置
    //printf("%d %d\n",a[left],key);
    a[left]=a[r];//a[left]=a[l];//也可以
    a[r]=key;
    fastsort(a,left,r-1);
    fastsort(a,l+1,right);
    return;
}
int main()
{
    int a[11];
    int n;
    int left=0,right=9;
    for(int i=0;i<10;i++)
    {
        scanf("%d",&a[i]);
    }
    fastsort(a,left,right);
    for(int i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}

晚上：
洛谷：Perket 才24分
//这个题做了两天了
（老实说那个第三组数据的结果有点不知道是得到的）