1.快速排序

时间复杂度O(nlogn)

主要思想：分治

1. 确定分界点x：一般为q[(l+r)>>1]
2. 调整区间：利用双指针使左区间全部<=x，右区间全部<=x。
3. 递归:先递归处理左区间，再递归处理右区间

模版

#include <iostream>

using namespace std;

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


void quick_sort(int q[],int l,int r){

    if(l>=r) return;

    int x = q[(l+r)>>1];
    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 n;
    scanf("%d", &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;
}

2.归并排序

时间复杂度O(nlogn)

主要思想：分治

1.确定分界点x：一般为(l+r)>>1
2.递归:先递归处理左区间，再递归处理右区间
3.归并:利用双指针把两个有序的数组合并成一个。两个指针分别指向有序数组的开始，并定义一个辅助数组存放合并结果
4.存回原数组对应序列

模版

#include <iostream>

using namespace std;

const int N=1e5+10;
int p[N];
int tmp[N];

void merge_sort(int p[],int l,int r){
    if(l>=r) return ;

    int x = (l+r)>>1; // 是范围的分界点！
    merge_sort(p,l,x);
    merge_sort(p,x+1,r);

    int i = l,j = x+1,k=0;
    while(i<=x&&j<=r){
        if(p[i]<p[j]) tmp[k++] = p[i++];
        else tmp[k++] = p[j++];
    }
    while(i<=x) tmp[k++] = p[i++];
    while(j<=r) tmp[k++] = p[j++];

    for (i = l, j = 0; i <= r; i ++, j ++ ) {
        p[i] = tmp[j];
    }
}
int main(){
    int n;
    scanf("%d",&n);

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

}