写在最前面：

此系列中的所有模板全为大佬所写，我只是一个搬运工（？）。

记录：

在之前学的所有最经典的排序方法中，理解简单是真简单，超时也是真超时......所以有了以下的算法。这几个方法速度应该是差不了多少的。

快速排序：

快速排序是先从数组中随意选择一个点，然后把该数字定为评判标准，比较其他数字和该数字的关系。如果比该数字大放在后面，小则放在前面（让大的和小的交换）。然后递归计算，最后将全部数字进行排序。

下面是模板：

#include <iostream>
#include<cstdio>
using namespace std;
int n;
int a[110000];
void quicksort(int *a,int l,int r)
{
    if(l>=r)//判断有一个数或者没有数字
        return;
    int x=a[l],i=l-1,j=r+1;//先运算后比较，所以比两头数据小
    while (i<j)
    {
        do i++;while (a[i]<x);//如果想要降序那么把符号改变即可
        do j--;while (a[j]>x);
        if(i<j)//用if表示判断
        swap(a[i],a[j]);
    }
    quicksort(a,0,j);
    quicksort(a,j+1,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    quicksort(a,0,n-1);
     for(int i=0;i<n;i++)
        printf("%d ",a[i]);
    return 0;
}

归并排序：

归并排序是稳定排序（快排不是），归并排序要使用到中间数组。先从中间划分好区间，然后用递归把前面的所有数据进行排序。在排序是把两个区间的数字按照顺序存到一个新的数组中，然后再次存回原来的数组，从而完成排序。

下面是模板：

#include <iostream>
#include<cstdio>
using namespace std;
int n;
int a[110000],tmp[110000];
void mergesort(int *a,int l,int r)
{
    if(l>=r)
        return;
    int mid =(l+r)>>1;//l+r的值右移1位，相当l+r的值除以2取整。
    mergesort(a,l,mid);
    mergesort(a,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j])
            tmp[k++]=a[i++];//运算完成后k自增1，i自增1
        else tmp[k++]=a[j++];
    }
    while (i<=mid)//注意等号
        tmp[k++]=a[i++];
    while (j<=r)
        tmp[k++]=a[j++];
    for(i=l,j=0;i<=r;i++,j++)
        a[i]=tmp[j];
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    mergesort(a,0,n-1);
    for(int i=0;i<n;i++)
    printf("%d ",a[i]);
    return 0;
}

其他排序：

在cstdlib里面的qsort和在algorithm里面的sort也是不错的选择。

qsort：(这里以整数数组为例）

qsort（数组名，数组成员个数，数据流行大小，cmp）；
int cmp（const void*a,const void *b）
{
   int* pa=(int*)a;
   int* pb=(int*)b;
   int num1=*pa;
   int num2=*pb;
   return num1-num2;//从大到小排序。
}

sort

sort默认的是从小到大排序，用法sort（开始的地址，结束的地址）如果需要其他排序方法，则sort（begin，end，cmp）cmp为特定的排序方法。

构体内嵌套比较函数

这个......就是解决在结构体内使用sort的问题。

struct node//结构体名
{
   int l,r;
   bool operator < (const node &a)const
   {
   return r<a.r;
   }
};

【算法】快速排序、归并排序