归并排序 刷题笔记

归并排序的写法

归并排序
分治+双指针

1.定义一个mid

if(l>=r)return ;

2.分治 

sort(q,l,mid);
sort(q,mid+1,r);
3.
双指针
int i=l,j=mid,k=0;
将双序列扫入 缓存数组
条件 while(i<=mid&&j<=r) 
两个数列比较大小 小的一方  进入缓存数组

4.
扫尾   
while(i<=mid) temp[k++]=q[i++];
while(j<=r)   temp[k++]=q[j++];

5.
复制  回去修改q[]数组的值

for (int i=l,j=0;i<=mid;i++,j++){
        q[i]= temp[j];
}
 

代码  

# include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<sstream>
const int N=1e5+10;
int q[N],temp[N];
int n;
void quick_sort(int q[],int l,int r){
    if(l>=r){
        return ;
    }
    int mid =(l+r)>>1;
    quick_sort(q,l,mid);
    quick_sort(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];
    }
} 
using namespace std;
int main(){
    int n;
    cin>>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;
}