一，计数排序

顾名思义，统计这个数出现多少次

#include<bits/stdc++.h>
using namespace std;
int a[1000];
int n,m;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		a[x]++;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=a[i];j++)cout<<i<<" ";
	}
	return 0;
}

二，选择排序

从n个数中选择更小的数与最前面的数交换

再从剩下n-1个数中重复此操作

以此类推

#include<bits/stdc++.h>
using namespace std;
int a[1000];
int n;
int main(){
	for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(a[j]<a[i])swap(a[j],a[i]);
        }
    }
	return 0;
}

三，冒泡排序

相邻比较后交换

for(int i=1;i<=n;i++){
	for(int j=1;j<=n-i;j++){
		if(a[j]>a[j+1])swap(a[j],a[j+1]);
    }
}

四，插入排序

从未排序的数中取出一个数，与已排序的数比较后插入

for(int i=2;i<=n;i++){
    int now=a[i];
	for(int j=i-1;j>=0;j--){
		if(a[j]>now){
			a[j+1]=a[j];
             a[j]=now;
         }eles break;
         a[j+1]=now;
    }
}

五，快速排序

注意，哨兵数可以被交换

void qsort(int l,int r){
    int mid=a[(l+r)>>1];//注意，此处一定要先储存中间数，而不是在下面判断用a[(l+r)>>1],因为后面交换时可能会交换中间数使其改变
    int i=l,j=r;
    while(i<=j){
        while(a[i]<mid)i++;
        while(a[j]>mid)j--;
        if(i<=j){
            swap(a[i],a[j]);
            i++;j--;
        }
    }
    if(l<j)qsort(l,j);
    if(i<r)qsort(i,r);
}

六，sort函数

int a[100010];
bool cmp(int x, int y){
	return x < y;
}
sort(a+l,a+r,cmp);//将a数组在[l,r)区间内从小到大排序

struct node{
	int x, y;
}c[1005];
bool cmp(node a, node b){
	if(a.x!=b.x){
		return a.x>b.x;//优先按x排序
	}
	return a.y>b.y; //x相等则按y排
}
sort(c+1,c+1001,cmp);

七，归并排序

讲一个$2n$序列拆成两个子序列，分别记为

$a_1,a_2,...a_n$

$b_1,b_2,...b_n$

然后设置两个指针$i,j$

假设现在有$2n$个空位

当$a_i<b_j时填入a_i，反之b_j$

完成一次这样的操作后的序列记为$c_i$​

不难发现，当a序列与b序列本身是单调递增时，二者归并得到的c序列也是单调递增的

因此为使a序列与b序列单调递增，便可以采用递归的方式拆分a,b,分解为若干子问题

复杂度$O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int ans[100010];
void solve(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    solve(l,mid);
    solve(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(k<=r){
        if(i>mid){
            ans[k]=a[j];
            j++;
        }else if(j>r){
            ans[k]=a[i];
            i++;
        }else if(a[i]<a[j]){
            ans[k]=a[i];
            i++;
        }else{
            ans[k]=a[j];
            j++;
        }
        k++;
    }
    for(int i=l;i<=r;i++)a[i]=ans[i];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    solve(1,n);
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
	return 0;
}