1：快速排序

先上模板

// 快速排序算法模板
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    
    int i = l - 1, j = r + 1, x = q[l];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
        else break;
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

然后是习题

785. 快速排序

快速排序的基本思想是基于分治
大致思想是
假设我们有一个集合q 左端点为l,右端点为r
我们现在集合确认一个分界点 m，m的常用取值有q[l],q[r],q[(l+r)/2] 或者区间内任意一个点都行
然后我们要做的就是 调整这个区间，使的区间的左侧ql[]都<=m区间的右侧qr[]都>=m
这样我们就对区间进行了一个初步的整理
然后我们要做的就是递归的去对 ql[],qr[]执行上述步骤 直到细分后的区间元素数量为1

所以快速排序的步骤就是：

1确定分界点 (常用的点有q[l] , q[r] , q[(l+r)/2])

2调整区间 使得左侧区间的值都小于等于m右侧区间的值都大于等于m

image.png

3递归处理左右两端

然后我们会发现 其中比较复杂的就是第二部 对区间进行处理

---

我们可以先讲一种逻辑上比较简单 比较暴力的做法：
我们可以新开两个数组用于存放所有<=m的值和所有>m的值
然后我们再将这两个数组中的值填入原数组
但这样我们需要一个额外的空间 而且做法比较暴力这里我们有一个比较巧妙的方法去解决这个问题

---

我们可以定义两个指针 i,j来对整个区间进行扫描 这里我们取m=q[l]=2

image.png
首先我们来看i指针指向的元素2 不满足q[i]<m(2) 因此指针i先停下来然后我们在依次看j指向的数5>2成立，2>2 不成立此时j也停下 此时 j>i 交换q[i]与q[j]
此时结果如下
image.png

然后我们继续
i指向1，1<2成立 i继续移动
i指向3，3<2不成立 i停止移动 j开始移动
j指向3，3>2成立，j继续移动
j指向1，1>2不成立 j停止运动
此时i=2,j=1 i>j 说名到这里我们已经扫描完成一遍元素了，并得到以下结果

image.png

由于i>j 所以我们可以保证在(l,j)区间内，所有的元素都被i指针扫描过一次 故所有的元素都小于等于m，同理在(j+1,r)中，左右的元素值都大于等于m
这样便完成了一次对数组的整理
之后我们分别对( l , j )和( j+1 , r )两个区间进行处理即可

然后我们来最开始习题的题解

#include<iostream>
using namespace std;

const int N=1e6+10;
int nums[N];

void QuickSort(int q[],int l,int r)
{
    if(l>=r)
        return;
    
    int mid=q[l],i=l-1,j=r+1;
    while(i<j)
    {
        do i++; while(q[i]<mid);
        do j--; while(q[j]>mid);
        if(i<j)
            swap(q[i],q[j]);
    }
    QuickSort(q,l,j);
    QuickSort(q,j+1,r);
}


int main()
{
    int count;
    scanf("%d",&count);
    
    for(int i=0;i<count;i++)
        scanf("%d",&nums[i]);
    
    QuickSort(nums,0,count-1);
    
    for(int i=0;i<count;i++)
        printf("%d ",nums[i]);
        
    return 0;
}

---

快速排序练习题：第K个数

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第k小数。

数据范围

1≤n≤100000,

1≤k≤n

输入样例：

5 3
2 4 1 5 3

输出样例：

3

先来分析一下这道题
给的是一个无序的数组，找到第k个数 首先想到的就是 先把整个数组 快排 然后输出低K个数
但这样其实我们相当于进行了很多多余的操作

// 快速排序算法模板
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    
    int i = l - 1, j = r + 1, x = q[l];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
        else break;
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

我们来看这个模板 每进行一次排序，他需要对左右两边都进行一次排序的操作。然而我们需要找到第K个数，所以我们只需要去对有第K个数的范围进行排序即可

例如 我们第一次排序后 将数组以j为边界分为了左右两侧，此时各个数据的值为

i=0 j=5 r=10 k=7，左侧的元素数量nl=j-1+1=6 小于k

那么我们只需要对 (j+1,r)范围内查找第k个 因为左侧的所有元素均小于等于右侧的所有元素
那么相当于 我们在左侧已经找过nl个数了 所以相当于在右侧查找 第 k-nl位元素 所以如果k在左侧区域，不需要跟新k， k在右侧区域内 对k进行更新

所以有

    if(j-l+1>=k)
        return QuickFind(q,l,j,k);
    else
    {
        k-=(j-l+1);
        return QuickFind(q,j+1,r,k);
    }

而因为我们每一次只对 存在k的一侧进行更新查找，所以当遇到 l>=r时，这个值就是我们要查找的元素

下面是题解

#include<iostream>
using namespace std;

const int N=1e6+10;
int nums[N];


int QuickFind(int q[],int l,int r,int k)
{
    if(l>=r)
        return q[l];
    
    int mid=q[l],i=l-1,j=r+1;
    while(i<j)
    {
        do i++; while(q[i]<mid);
        do j--; while(q[j]>mid);
        if(i<j)
            swap(q[i],q[j]);
    }
    if(j-l+1>=k)
        return QuickFind(q,l,j,k);
    else
    {
        k-=(j-l+1);
        return QuickFind(q,j+1,r,k);
    }
}

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    
    for(int i=0;i<n;i++)
        scanf("%d",&nums[i]);
        
    int res= QuickFind(nums,0,n-1,k);
    
    printf("%d",res);
}

---

2：归并排序

先上算法模板

// 归并排序算法模板
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];
}

归并排序的思想也是基于分治 但和快速排序不同的是，归并排序是一种稳定的排序算法 而且归并排序的时间复杂度无论任何情况都是 n(logn) 而快速排序的平均时间复杂度为n(logn) 最坏情况下为 n^2
(关于排序算法是不是稳定 指的是： 当一个排序过程中有两个相等的元素时 排序结束后如果两个元素的前后关系可能会发生变化那么就是 不稳定的 而如果不会变化就是稳定的 快速排序就是一种不稳定算法 当然我们也可以通过操作来将不稳定算法变为稳定算法 例如快速排序，我们可以在只对值排序的基础上增加上下标， 变成pair<值，下标> 对pair来进行排序 这样我们就可以保证里面所有的值都是唯一的)

归并排序的思想为 以下三部

• 每次讲待排序的数组从中间分为左右两个数组
• 将两个数组分别排序
• 将两个有序的数组合二为一

我们可以发现，步骤中比较复杂的为第三部 合二为一 这里我们可以使用双指针算法 过程如下

image.png

开始时先创键 i 和 j两个指针
然后在过程中我们用这两个指针对数组进行扫描，判断
若 a[i]<=b[j] 我们便将a[i]存入，并将i++
若 a[i]>b[j] 我们便将b[j]存入，并将j++

当 i 或者 j 扫描到末尾时，我们停止扫描。
此时我们再看
若 i<a.lengh 说名a中有元素没有全部放入有序数组中，我们将a中的剩余元素放入
若 j<b.lengh 说名b中有元素没有全部放入有序数组中，我们将b中的剩余元素放入

在排序中我们需要开辟一个新的临时数组temp来存放合并后的数组，在合并完成后我们 temp中的数据放回原数组当中

来看一道习题 787. 归并排序

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000
输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

思路上面都讲过了下面直接上代码

#include<iostream>
using namespace std;

const int N=1e6+10;

int q[N],temp[N];


void MergeSort(int q[],int l, int r)
{
    if(l>=r)
        return;
    
    int mid=l+r>>1;
    
    MergeSort(q,l,mid);
    MergeSort(q,mid+1,r);
    
    int i=l,j=mid+1,k=0;
    
    while(i<=mid && j<=r)
    {
        if(q[i]<=q[j])
            temp[k++]=q[i++];
        else
            temp[k++]=q[j++];
    }
    while(i<=mid)   temp[k++]=q[i++];
    while(j<=r)     temp[k++]=q[j++];
    
    for(int i=l,j=0;i<=r;i++,j++)
    {
        q[i]=temp[j];
    }
}


int main()
{
    
    int n;
    scanf("%d",&n);
    
    for(int i=0;i<n;i++)
    {
        scanf("%d",&q[i]);
    }
    
    MergeSort(q,0,n-1);
    
    for(int i = 0;i < n;i++)
    {
        printf("%d ",q[i]);
    }
    
   
    return 0;
}

第二道习题 788. 逆序对的数量

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000
输入样例：

6
2 3 4 5 6 1

输出样例：

5

题解：

这道题直接一看很麻烦其实只需要按照上面归并排序中的一步 当我们每次发现 a[i]>b[j]时
说名[a[i]),a[mid]]中所有元素均大于b[j] 所以 每次讲b数组中的元素放入时，我们就相当于找到了mid-i+1 个逆序对

上代码

#include<iostream>
using namespace std;

const int N=1e6+10;

int q[N],temp[N];

long long cnt;


void MergeSort(int q[],int l,int r)
{
    if(l>=r)
        return;
    int mid=l+r>>1;
    MergeSort(q,l,mid);
    MergeSort(q,mid+1,r);

    int k=0,i=l,j=mid+1;
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j])
            temp[k++]=q[i++];
        else
        {
            cnt+=(mid-i+1);
            temp[k++]=q[j++];
        }
    }
    while(i <= mid) temp[k++]=q[i++];
    while(j <= r)  temp[k++]=q[j++];
    
    for(int i=l,j=0;i<=r;i++,j++)
        q[i]=temp[j];
}


int main()
{
    int n;
    
    scanf("%d",&n);
    
    for(int i=0;i<n;i++)
        scanf("%d",&q[i]);
        
    MergeSort(q,0,n-1);
    
    cout<<cnt;
}

2：二分

二分在整出查找里面是一种接近万能的算法 并且对应两个模板
一个是区间为[l,mid][mid+1,r] 一个是[l,mid-1],[mid,r]
这里之前有一个详细的帖子对二分进行整理就不多赘述了 二分讲解

直接来看习题

789. 数的范围

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

如果数组中不存在该元素，则返回“-1 -1”。

输入格式

第一行包含整数n和q，表示数组长度和询问个数。

第二行包含n个整数（均在1~10000范围内），表示完整数组。

接下来q行，每行包含一个整数k，表示一个询问元素。

输出格式

共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回“-1 -1”。

数据范围

1≤n≤100000
1≤q≤10000
1≤k≤10000

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

#include<iostream>
using namespace std;

const int N=1e6+10;

int a[N];



int FindUp(int q[],int tar,int n)
{
    int res=-1;
    int l=0,r=n-1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(q[mid]>=tar)
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    if(q[l]==tar)
        res=l;
    return res;
}
int FindDown(int q[],int tar,int n)
{
    int res=-1;
    int l=0,r=n-1;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(q[mid]<=tar)
        {
            l=mid;
        }
        else
        {
            r=mid-1;
        }
    }
    if(q[l]==tar)
        res=l;
    return res;
}


int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    
    for(int i=0;i<q;i++)
    {
        int tar;
        scanf("%d",&tar);
        int res=FindUp(a,tar,n);
        if(res==-1)
            cout<<"-1 -1"<<endl;
        else
            cout<<res<<" "<<FindDown(a,tar,n)<<endl;
    }
}

直接上代码
题目要求是求给定有序数组里面数出现的范围，而我们二二分模板两个刚好是查找 最左端和最右端 所以直接用两个二分分别找到左端和右端的地址输出即可

浮点数二分

先上题目790. 数的三次方根

给定一个浮点数n，求它的三次方根。

输入格式

共一行，包含一个浮点数n。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留6位小数。

数据范围
−10000≤n≤10000

输入样例：

1000.00

输出样例：

10.000000

浮点数二分的过程就是 我们先根据题意找到合适的 l r
例如这道题，数据范围是-10000~10000

我们可以先大概对左右两个端点的三次方根秋一下
303030=9000 404040=16000
所以我们可以把 l 和 r 定为-40和40
然后我们再看输出格式 要求保留小数点后六位
一般情况下 最好多计算两位保证精度不会缺失
然后上代码

#include<iostream>
using namespace std;

int main()
{
    double i=-100,j=100;
    
    double n;
    cin>>n;
    
    while(j-i>1e-8)
    {
        double mid=(i+j)/2;
        if(mid*mid*mid<n)
        {
            i=mid;
        }
        else
            j=mid;
    }
    printf("%.6f",i);
}