排序

快速排序

主要思想: 分治

实现步骤

  1. 确定分界点: q[l],q[(l+r)/2],q[l],随机.(四种任选一种)
  2. 调整区间
  3. 递归处理左右两段

复杂度分析

  • 时间复杂度: O(nlogn)O(nlogn)
  • 空间复杂度: O(logn)O(logn)

模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
using namespace std;

const int N=1e5+10;

int q[N];

void quick_sort(int l,int r){
    //终止条件
    if(l>=r) return ;
    //确定分界点
    int x=q[l+r>>1],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(l,j);
    quick_sort(j+1,r);
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>q[i];

    quick_sort(0,n-1);

    for(int i=0;i<n;i++) cout<<q[i]<<' ';
    return 0;
}

模板题:
快速排序(洛谷)
进阶:
数组中的第K个最大元素(leetcode)

归并排序

主要思想: 分治

实现步骤:

  1. 确定分界点: mid=(l+r)/2.
  2. 递归排序左右两边.
  3. 归并-----合二为一.

复杂度分析

  • 时间复杂度: O(nlogn)O(nlogn)
  • 空间复杂度: O(n)O(n)

模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
using namespace std;

const int N=1e5+10;

int q[N];
int tmp[N];

void merge_sort(int l,int r){
    //终止条件
    if(l>=r) return;
    //确定分界点
    int mid=l+r>>1;
    //递归排序左右两边
    merge_sort(l,mid);
    merge_sort(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;
    cin>> n;
    for(int i=0;i<n;i++) cin>>q[i];

    merge_sort(0,n-1);

    for(int i=0;i<n;i++) cout<<q[i]<<' ';

    return 0;
}

模板题:
归并排序(洛谷)

二分

整数二分

主要思想: 每次划分区间后舍弃答案不在的区间,从而快速缩小范围找到答案

条件: 区间的二义性

二义性: 存在某种性质可以将区间一分为二.例如: 一个单调的数列,从中选择一个数,则这个数列一定会被分为两个区间,要么大于等于这个数和小于这个数,要么小于等于这个数和大于这个数,可以这么认为单调性是二分的一份子集.

复杂度分析

  • 时间复杂度: O(logn)O(logn)
  • 空间复杂度: O(1)O(1)

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            if(!nums.size()) return {-1,-1};
            int l=0,r=nums.size()-1;
            vector<int> res;
            //二分下边界
            while(l<r){
                int mid=r+l>>1;
                if(nums[mid]>=target) r=mid;
                else l=mid+1;
            }
            if(nums[l]!=target) return {-1,-1};
            res.push_back(l);
            l=0,r=nums.size()-1;
            //二分上边界
            while(l<r){
                int mid=l+r+1>>1;
                if(nums[mid]<=target) l=mid;
                else r=mid-1;
            }
            res.push_back(l);
            return res;
        }
};

模板题:
在排序数组中查找元素的第一个和最后一个位置

浮点数二分

浮点数二分比较简单,这里直接给出模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool check(double x){/*....*/} //检查x是否满足某种性质

double bsearch(double l,double r){

    double eps = 1e-6;//根据题目设置精度

    while(r-l<eps)
    {
        double mid=(r+l)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }

    return l;
}