写点什么

排序与二分

用户头像
落曦
关注
发布于: 2020 年 11 月 23 日

学习算法的主要方法

  1. 背过代码模板

  2. 一个题目的代码写 3~5 遍


快速排序——分治

  1. 确定分界点:q[l],q[(l+r)/2],q[r],随机选择一个点

  2. 调整区间,将第一个区间内所有的数都小于等于 x,第二个区间内所有的数都大于等于 x。(中间数不一定是 x)

  3. 递归处理左右两段


image.png


开始 i 指向的数≤x,j 指向的数≥x,一旦不成立 i 和 j 的数进行交换,直到 i 和 j 相遇

无论在什么时候 i 前面的数都是≤x,j 后面的所有数≥x

快排模板

#include<iostream>using namespace std;const int N=1000010;int n;int q[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);        if(i<j)swap(q[i],q[j]);    }    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]);    quick_sort(q,0,n-1);    for(int i=0;i<n;i++)printf("%d ",q[i]);    return 0;}
复制代码

归并排序——分治

  1. 确定分界点:mid=(l+r)/2

  2. 递归排序 left,right

  3. 归并——合二为一


image.png


image.png


左右端比较循环扫描。

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[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; 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 (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];}
int main(){ int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
return 0;}
复制代码

拓展

归并排序是稳定的,快速排序是不稳定的。

稳定:原序列两个数是相同的,排序之后两个数的位置不发生变化是稳定的,否则是不稳定的。

将快排中所有的数都变成不同的数时,快排就可以变为稳定的排序。

二分

重点:二分的本质并不是单调性,有单调性一定可以二分,二分不一定需要单调性。

整数二分


image.png


满足在红色区域时

  1. mid=l+r+1>>1

if(check(mid)) true [mid,r],l=mid

false [l,mid-1],r=mid-1

int l = 0, r = n - 1;while (l < r) {        int mid = l + r + 1 >> 1;        if (a[mid] <= x) l = mid;        else r = mid - 1; }
复制代码

满足在绿色区域时

  1. mid=l+r>>1

if(check(mid)) true [l,mid],r=mid

                     false [mid+1,r],l=mid+1

int l = 0, r = n - 1;while (l < r) {    int mid = l + r >> 1;    if (a[mid] < x)  l = mid + 1;    else    r = mid;}
复制代码

浮点数二分

不需要考虑上述的边界问题,直接二分

#include<iostream>using namespace std;int main(){    double x;    cin>>x;    double l=0,r=x;    while(r-l>1e-8){        double mid=(l+r)/2;        if(mid*mid>=x)r=mid;        else l=mid;    }    printf("%lf\n",l);    return 0;}
复制代码


用户头像

落曦

关注

还未添加个人签名 2019.03.25 加入

还未添加个人简介

评论

发布
暂无评论
排序与二分