快排/归并/二分

排序

• 快速排序

  • 主要思想：分治
  • 排序方式：
    • 确定分界点：左边界：q[l], 中间值：q[(l+r)/2],右边界，或者随机
    • 调整区间：小于等于x的在x左半边，大于等于x的在x右半边（最难的部分）
      • 法一：
        • 开a[],b[]
        • 扫描一遍q[] ，q[i]>=x q[i]->a[]; q[i]<=x q[i]->b[];
        • a[]->q[] b[]->b[]
      • 法二（更优美）：
        • 两个指针i，j，i指向左端,j指向右端
        • i,j同时往中间走
        • 如果q[i]<x,i++,如果q[i]>x,移动j
        • 如果q[j]>x,j--,如果q[j]<x,此时交换q[i]与q[j]
        • 交换完之后，i++,j--
    • 递归处理左右两段
  • 模板：平均时间复杂度nlog2(n)

    void quick_sort(int q[], int l, int r){
    	if(l >= r) return ;
    	int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    	while(i < j){
    		//do ++ i; while(q[i] < x);
    		//do -- j; while(q[j] > x);
    		while(q[++i] < x);
    		while(q[--j] > x);
    		if(i < j) swap(q[i], q[j]);
    	} 
    	quick_sort(q, l, j);
    	quick_sort(q, j + 1, r);
    	//x取q[l] ,sort(q,l,j),sort(q,j+1,r);
    	//x取q[r] ,sort(q,l,i-1);sort(q,i,r);
    	//x取q[(r+l+1)/2],sort(q,l,i-1);sort(q,i,r);
    	//x取q[(r+l)/2],sort(q,l,j),sort(q,j+1,r);
    	//总之x取右边界，sort取左指针
    	//x取左边界，sort取右指针
    }
    

• 归并排序

  • 主要思想：分治
  • 排序方式：
    • 确定分界点：mid = （l + r）/2
    • 递归排序左右两段
    • 合并左右两段: 双指针
  • 模板：时间复杂度nlog2(n)

    void merge_sort(int q[], int l ,int r){
    	if(l >= r) return ;
    	int mid = l + r >> 1;
    	merge_sort(l, mid);
    	merge_sort(mid + 1, r);
    	int k = 1, i = l, j = mid + 1;
    	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 ++];
    	for(int i = l, j = 1; i <= r; ++ i, ++ j)
    		 q[i] = tmp[j];
    }
    

二分查找

    - 可以找到满足区间与不满足区间的边界点

• 整数二分

  • 模板：

    //找最小
    int binary(int l, int r){
    	while(l < r){
    		int mid = r + l >> 1;
    		if(check(mid)) r = mid;
    		else l = mid + 1;
    	}
    	return l;
    }
    //找最大
    int binary(int l , int r){
    	while(l < r){
    		int mid = r + l + 1 >> 1;
    		if(check(mid)) l = mid;
    		else r = mid - 1;
    	}
    	return l;
    }
    

• 浮点数二分

  • 模板

    	//浮点数二分模板一：
    void binary(int x){
        double l = 0, r = 1000;
        while(r - l > 1e-9){
            double mid = (r + l) / 2;
            if(mid*mid*mid < x) l = mid;
            else r = mid; 
        }
        printf("%.6f",l);
        return ;
    }
    
    //浮点数二分模板二：
    void binary(int x){
        double l = 0, r = 1000;
        for(int i = 1; i < 100; i ++){
            double mid = (r + l) / 2;
            if(mid*mid*mid < x) l = mid;
            else r = mid; 
        }
        printf("%.6f",l);
        return ;
    }