AcWing打卡第一课 排序+二分

AcWing打卡第一课 排序+二分 排序 1.快速排序

快排是基于分治的
	-1.确定分界点x,常用的是l左,r右,(l+r)/2中间
    -2.调整区间，使得第一个区间里面的数都小于等于x，第二个区间里面的数都大于等于x
    	-方法1：开两个额外的数组a b
    		-把小于等于x的数放入a中
    		-把大于x的数放入b中
    		-再把a和b的数放回q中，这时q中左边的数都小于等于x，右边的数都大于x
    	-方法2：使用两个指针i j指向两边，同时往中间走
    		-i先往中间走，如果是小于等于x的不用处理，大于x的时候，停下来
    		-j往中间走，如果是大小x的就不用处理，小于等于x的时候，停下来
    		-i和j进行交换，然后i++，j--
    		-当i大于j的时候，这个q区间中所有的数都满足左边的数小于等于x，右边的数大于x了
	-3.递归【递归给左边排序，递归给右边排序】
    	
#include 

const int N = 1e6+10;

int n;
int q[N];

void quick_sort(int q[],int l,int r){
    if(l >= r) return; // 如果只剩下一个数 或者越界了没数了 那就直接reutrn 
    int x = q[l], i = l-1, j = r+1;
    while(i < j){ // 当左边的指针还没超过右边的时候 
        do i++;while(q[i] < x); // 直到找到大于等于分界点的数
        do j--;while(q[j] > x); // 直到找到小于等于分界点的数
        // 如果还没有顺序 那么 i 肯定是小于 j的 如果已经有序了 那么就不用进行交换了
        if(i < j) swap(q[i],q[j]);
    }
    // 经过上面的步骤 左边一定小于等于x  右边一定大于等于x 那么再递归对子序列进行排序
    // 直到序列都只剩下一个元素了 那么就是有序的了
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

int main(){
    scanf("%d",&n);
    for(int i = 0; i < n; i++) scanf("%d",&q[i]); // 循环录入n个数据

    quick_sort(q,0,n-1); // 进行快速排序

    for(int i = 0; i < n; i++) scanf("%d",q[i]); // 循环输出数据

    return 0;
}

2.归并排序

归并排序的主要思想也是分治
    -1.以中间为分界点 mid = (l+r)/2，分为左边和右边
    -2.递归排序左边和右边
    -3.排完序以后，左边和右边就都有序了，然后我们进行归并，两个有序的合为一个有序的
    	-两个指针分别指向两个序列的开头即两个序列的分别最小值，然后额外一个新的数组用来存放结果
    	-然后两个指针分别比较，每次我们都可以取出一个最小值出来存到新的数组中，直到两个数组的数都用完了，那么这个新的数组就是结果
   	 
#incldue

cosnt int N = 1e6 + 10;

int n;
int q[N],tmp[N];

void merge_sort(int q[],int l,int r){
    if(l >= r) return;
    int mid = (l+r) >> 1; // 分界点
    // 递归左边 递归右边
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);
    // 归并
    int k = 0,i = l, j = mid + 1; // i左半边起点 j右半边起点
    while(i <= mid && j <= r){
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    // 把剩下的拿出来
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    // 把结果存回q中
    for(i = l,j = 0;i <= r;i++,j++) q[i] = tmp[j];
}

int main(){
    scanf("%d",&n);
    for(int i = 0; i < n; i++) scanf("%d",&q[i]);

    merge_sort(q,0,n-1); // 归并排序

    for(int i = 0; i < n; i++) printf("%d",q[i]);
    return 0;
}

查询 1.二分【整数/小数】

有单调性的一定可以二分，而没有单调性的题目也有可能可以二分，并不是说没有单调性就不能二分。二分的本质并不是单调性。
    
二分的本质是边界。即如果在l->r这个区间，我们找到某种性质，使得在右半边区间这个性质是满足的，而在左半边的区间是不满足的，整个区间可以一分为二，如果我们可以找到这样的性质的话，使得我们可以把这个区间一分为二，一半满足，一半不满足，二分就可以寻找边界，既可以寻找红色右边这个点，也可以寻找绿色左边这个点。所以二分的本质就是在区间找性质。

红色点
mid = (l+r+1)>>1，然后判断中间值是否满足性质
    -true 则mid一定在红色区间里
    	-[mid,r] l = mid
    -false 则mid一定在绿色区间
    	-[l,mid-1] r = mid-1
    
绿色点
mid = (l+r)>>1，然后判断中间值是否满足性质  
    -true 则mid一定在绿色区间里
    	-[l,mid] r = mid
    -false 则mid一定在红色区间
    	-[mid+1,r] l = mid+1
    
int bsearch_1(int l, int r) 
{
    while (l < r) //  找到大于等于x的最小的数 即左边
    {
        int mid = l + r >> 1;
        if (大于等于x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch_2(int l, int r) 
{
    while (l < r) //  找到小于等于x的最大的数 即右边
    {
        int mid = l + r + 1 >> 1;
        if (小于等于x) l = mid;
        else r = mid - 1;
    }
    return l;
}
上面两种模板 代表不同情况

求数的范围 
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
如果数组中不存在该元素，则返回 -1 -1。
    
#include 

using namespace std;

const int N = 1e6+10;

int n,m;
int q[N];

int main(){
    scanf("%d%d",&n,&m);
    // 输入数据
    for(int i = 0; i < n; i++) scanf("%d",&q[i]);
    // 要找几个数的最大和最小
    while(--m){
        int x;
        scanf("%d",&x);

        int l = 0, r = n-1;
        // 找大于等于x的最小数 即左边
        while(l < r){
            int mid = l + r >> 1;
            if(q[mid] >= x) r = mid; // 如果中间的数比我要找的还大 我要找的在左边
            else l = mid+1; // 如果中间的数比我要找小  我要找的在右边
        }

        if(q[l] != x) cout << "-1 -1" << endl;
        else{
            cout << l << " ";

            int l = 0, r = n - 1;
            // 找小于等于x的最大数 即右边
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(q[mid] <= x) l = mid; // 如果中间的数比我要找的小 我要找的在右边
                else r = mid - 1; // 如果中间的数比我要找的大 我要找的在左边
            }
            cout << l << " ";
        }
    }

    return 0;
}
 
小数二分
int bsearch_3(double l,double r)
{
    double eps=1e-5;  //一般eps=1e-(k+2)，k为精确度
    while(r-l>eps)
    {
        double mid=r+l/2;
        if(check(mid)) r=mid;
        else   l=mid;
    }
    return l;
}
模板
  
给定一个浮点数，求它的三次方根。
    
#include 

int main(){
    double x;
    scanf("%lf",&x);

    double l = 0, r = x;
    while(r - l > 1e-6){ // 要保留多少位小数就-多少位小数再多2
        int mid = l + r >> 2;
        if(mid * mid * mid >= x) r = mid; // 在左边
        else l = mid + 1; // 在右边
    }
    printf("%lf",l);
}