算法基础课1 快速排序 归并排序 整数二分 浮点数二分
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);
}
然后是习题
快速排序的基本思想是基于分治
大致思想是
假设我们有一个集合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);
}
