排序（提高级）
题单介绍
下列排序中归并排序和快速排序需要会写，其他需要了解其实现方式。
归并排序：
归并排序是一种分治的思想。先把整个数组分成前后两部分，把两部分都排完之后再将其合并起来。至于这两部分的排序方法，则是递归进行归并排序，直到将其分解到一个数为止。
而当左右两部分都排序好后，那么合并时只需要像选择排序一样每次取出其中的最小值即可。而归并排序使左右两部分已经排好序了，那么这个最小值只用在这两部分的最前面的元素里选。
```cpp
int a[maxn],b[maxn];//a为原数组，b为临时数组
void mergesort(int l,int r){
if(l==r)return ;
int mid=(l+r)>>1;
mergesort(l,mid);//左边一半排序
mergesort(mid+1,r);//右边一半排序
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){//每次挑选小的，直到一边没有数为止
if(a[i]<=a[j])b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=mid)b[k++]=a[i++];//把剩余的数移入b数组
while(j<=r)b[k++]=a[j++];
for(int i=0;i<k;i++)a[l+i]=b[i];//把数移回a数组
}
```
快速排序：
快速排序的想法与归并排序类似。快速排序会先将一个数作为基准，将比他小的数移到左边，比他大的数移到右边。然后左右分别排序。
```cpp
void quicksort(int l,int r){//见动画演示
if(l>=r)return;
int now=l;
for(int i=l+1;i<=r;i++){
if(a[i]<a[l]){
now++;
swap(a[i],a[now]);
}
}
swap(a[l],a[now]);
quicksort(l,now-1);
quicksort(now+1,r);
}
```
堆排序：建立一个空的堆，然后把所有元素push进堆，再把所有元素拿出来，就能得到一个有序的数列。
[锦标赛排序](https://blog.csdn.net/Acx77/article/details/116852010)
基数排序（见动画演示）
[桶排序](https://blog.csdn.net/sinat_31275315/article/details/107868240)
[排序算法的动画演示](https://visualgo.net/zh/sorting)