快排 归并

[快排] [c++]

#include<bits/stdc++.h>
using namespace std;

const int N =1e6+10;
int n,q[N];
void quick_sort(int q[],int l,int r) //l r指起点终点索引
{
    if (l>=r) return;
    int x=q[l],//确定分界点
    int 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);
}
int main()
{
    int m;
    cin>>m;
    for(int i=0;i<m;i++) cin>>q[i];
    quick(q,0,m-1);
    for(int j=0;j<m;j++) cout<<q[j]<<" ";
    return 0;
}
1.确定分界点（通常l） 2.调整区间 3.递归处理两侧

[归并] [c++]

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int mid=1+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++]=j[i++];
    for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}
int main()
{
    int m;
    cin>>m;
    for(int i=0;i<m;i++) cin>>q[i];
    merge_sort(q,0,m-1);
    for(int j=0;j<m;j++) cout<<q[j]<<" ";
    return 0;
}
1.确定分界点 2.递归排序 3.归并