排序与二分

落曦

关注

发布于: 2020 年 11 月 23 日

学习算法的主要方法

背过代码模板
一个题目的代码写 3~5 遍

快速排序——分治

确定分界点：q[l],q[(l+r)/2],q[r],随机选择一个点
调整区间，将第一个区间内所有的数都小于等于 x，第二个区间内所有的数都大于等于 x。（中间数不一定是 x）
递归处理左右两段

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;}

复制代码

归并排序——分治

确定分界点：mid=(l+r)/2
递归排序 left,right
归并——合二为一

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

满足在红色区域时

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; }

复制代码

满足在绿色区域时

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;}

复制代码

发布于: 2020 年 11 月 23 日阅读数: 17

落曦

关注

还未添加个人签名 2019.03.25 加入

还未添加个人简介

发布

暂无评论

创作场景

排序与二分

学习算法的主要方法

快速排序——分治

快排模板

归并排序——分治

拓展

二分

整数二分

浮点数二分

落曦

评论