1.1排序（分治）
- 本讲主要概括快排和归并排序，代码及模板如下
1.1.1快速排序
- 用数来分，再递归。先分再递归
快排.png
void quick_sort(int q[],int l,int r)
{
if(l>=r)return;//判断边界
int i=l-1,j=r+1,x=q[(i+j)>>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(q,l,j);
quick_sort(q,j+1,r);
}
- 可以以 3 1 2 3 5 为例 举例说明
- 处理边界问题（待补充）
- 数据比较大的时候 scanf 更快一点 （或者写上待补充）
1.1.2 归并排序
- 确定分界点（以数组中间位置来分），先递归，再归并。（合二为一）
#include<iostream>
using namespace std;
const int N=1e6+10;
int q1[N];
void merge_sort(int q[],int l,int r){
if(l>=r)return;
int mid=(l+r)>>1;//注意 该处不能用(l+r+1)>>2
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(q[i]<q[j]){
q1[k]=q[i];
k++,i++;
}else{
q1[k]=q[j];
k++,j++;
}
}
while(i<=mid){
q1[k]=q[i];
k++,i++;
}
while(j<=r){
q1[k]=q[j];
k++,j++;
}
for(int i=l,j=0;i<=r;i++,j++){
q[i]=q1[j];
}
}
int main()
{
int n,q[N];
cin>>n;
for(int i=0;i<n;i++){
cin>>q[i];
}
merge_sort(q,0,n-1);
for(int i=0;i<n;i++){
cout<<q[i]<<" ";
}
return 0;
}
- 逆序对数量
#include<iostream>
using namespace std;
const int N=1e6+10;
int q[N],tmp[N];
int merge_sort(int q[],int l,int r){
if(l>=r) return 0;
int res;
int mid=(l+r)>>1;
res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(q[i]<=q[j]){//注意此处是小于等于
tmp[k++]=q[i++];
}else{
tmp[k++]=q[j++];
res+=mid-i+1;
}
}
while(i<=mid)tmp[k++]=q[i++];
while(j<=r)tmp[k++]=q[j++];
for(int i=l,j=0;i<=r;i++,j++){
q[i]=tmp[j];
}
return res;
}
int main()
{
int n,res;
cin>>n;
for(int i=0;i<n;i++){
cin>>q[i];
}
res=merge_sort(q,0,n-1);
// for(int i=0;i<n;i++){
// cout<<q[i]<<" ";
// }
cout<<res;
}
1.1.3 时间复杂度
- 时间复杂度为
排序时间复杂度.png
