这节东西有点小多，我打算分几次更完。
排序算法很多，选择排序插入排序冒泡排序堆排序归并排序快速排序等等
所以我准备先展示几个模板代码然后再通过其他题展示排序算法的应用
接下来是三个复杂度为n^2的排序算法
冒泡排序
不断进行相邻数的前后调换最终达到排序的目的，核心代码如下
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=1;i<=n;i++)
{
int maxx=1;//默认最值为a[1]，maxx记录的是下标
for(int j=2;j<=n-i+1;j++)
{
if(a[j]>a[maxx]) maxx=j;
}
swap(a[maxx],a[n-i+1]);
}
插入排序
将没有排序过的数插入到已经排序了的数里面，找到位置后break即可
for(int i=1;i<n;i++)
{
for(int j=i+1;j>=1;j--)
{
if(a[j-1]>a[j]) swap(a[j-1],a[j]);
else break;
}
}
这三个应该是最基础的排序算法了，不过我之前这里面是只会冒泡的，哎呀毕竟有sort也基本用不上......不过到了现在终究还是补上了
快速排序
思想和二分有点类似，。简单来说就是每次从数列中随机取出来一个数x，然后对所有数分为大于x等于x小于x三类。接着再分别对大于x和小于x两类的数列进行相同的操作。直到最终数列只剩一个数为止
至于实现方法，就是开四个数组，一个原数组，三个数组存三类数。每次分类时将数存进三个数组里。在每次遍历完数组后再用三个数组里的数更新原数组，平均而言复杂度是nlogn
这里我卡了挺久最后发现是随机数取错了，唉，铸币。
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005],c[100005],d[100005];
int randx(int l,int r)
{
return a[rand()%(r-l+1)+l];
}
void qsort(int l,int r)
{
//为了防止a数组在中途就改变，先改变其他数组
//全改变完后再赋值给A
if(l>=r) return;
int x=randx(l,r);
int cntb=0,cntc=0,cntd=0;
//cout<<x<<' ';
for(int i=l;i<=r;i++)
{
if(a[i]<x) b[++cntb]=a[i];
else if(a[i]==x) c[++cntc]=a[i];
else if(a[i]>x) d[++cntd]=a[i];
}
// cout<<x<<endl;
int cnb=0,cnc=0,cnd=0;
for(int i=l;i<=r;i++)
{
if(cnb<cntb) cnb++,a[i]=b[cnb];
else if(cnc<cntc) cnc++,a[i]=c[cnc];
else if(cnd<cntd) cnd++,a[i]=d[cnd];
}
//cout<<l<<' '<<r<<' '<<cnb<<' '<<cnc<<' '<<cnd<<endl;
qsort(l,l+cntb-1);
qsort(l+cnc+cnb,r);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
qsort(1,n);
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
return 0;
}