1 冒泡排序
比较相邻元素，将大的数往后移，这样一次操作就将大的数移到了后面。
时间复杂度为O(n2)
稳定排序

void bubble_sort(vector<int>&q)
{
    for(int i=q.size()-1;i>0;i--)//排序数据摆放位置
        for(int j=0;j+1<=i;j++)
            if(q[j]>q[j+1]) swap(q[j],q[j+1]);//前面的数比后面的数大，将数往后移
}

//优化操作，设置一个flag,一次遍历后如果数据都没发生移动，则可以停止

for(int i=q.size()-1;i;i--)
{
    bool flag=true;
    for(int j=0;j+1<=i;j++)
    {
        if(q[j]>q[j+1])
        {
            swap(q[j],q[j+1]);
            flag=false;
        }
    }
    if(!flag) break;
}

2.选择排序
找到最小的元素，然后与队列开头交换一下。这个算法和冒泡差别不大，就是减少了交换的次数，每次遍历最多只交换一次。
时间复杂度为O(N2)
不稳定

    void  select_sort(vector<int>&q)
    {
        for(int i=0;i+1<q.size();i++)
        {
            int idx=i;
            for(int j=i+1;j<q.size();j++)
                if(q[j]<q[idx]) idx=j;
            if(idx!=i) swap(q[i],q[idx]);
        }
    }

3.插入排序
从后往前找，如果当前的数大于我们要插入的数，就将当前的数往后移一位。
（1）最坏的时间复杂度为O(n2),就是所有的数都是倒序排列，每插入一个数都有移动全部的数
（2）最好的情况是O(N),所有的数都是从小到大排列，不需要移动数组。
稳定性：稳定

void insert_sort(vector<int>&q)
{
    for(int i=1;i<q.size();i++)
    {
        int t=q[i],j;
        for(j=i-1;j>=0;j--)
        {
            if(q[j]>t) swap(q[j],q[j+1]);
            else break;
        }
        q[j+1]=t;
    }
}

4 希尔排序 一般不考
5 归并排序
分治，自顶向下，递归的做法，自低向上，循环（力扣上148题）
时间复杂度O(Nlg(N)).
空间复杂度：O（LgN）+O(N)

void merge_sort(vector<int>&q,int l,int r)
{
    if(l>=r) return ;
    int mid=l+r>>1;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);

    static vector<int>t;//申请了全局变量
    t.clear();

    int i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j])
        {
            t.push_back(q[i]);
            i++;
        }
        else{
            t.push_back(q[j]);
            j++;
        }
    }
    while(i<=mid)
    {
        t.push_back(q[i]);
        i++;
    }
    while(j<=r)
    {
        t.push_back(q[j]);
        j++;
    }

    for(int i=l,k=0;i<=r;i++) q[i]=t[k++];
}

利用归并排序求逆序对？

int merge_sort(vector<int>&q,int l,int r)
{
    if(l>=r) return 0;
    int res=0;

    int mid=l+r>>1;
    res+=merge_sort(q,l,mid);//内部的逆序对
    res+=merge_sort(q,mid+1,r);

    static vector<int>t;//申请了全局变量
    t.clear();

    //求外部的逆序对
    int i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j])
        {
            t.push_back(q[i]);
            i++;
        }
        else{
            res+=(mid-i+1);
            t.push_back(q[j++]);
        }
    }
    while(i<=mid)
    {
        t.push_back(q[i]);
        i++;
    }
    while(j<=r)
    {
        t.push_back(q[j]);
        j++;
    }

    for(int i=l,k=0;i<=r;i++) q[i]=t[k++];
}

6 快速排序
从整个数列中随机挑一个数，将数列中大于这个数放到右边，小于这个数的放到左边。
平均时间复杂度为O(Nlg(N))
空间复杂度为lg（N）,不稳定

最坏时间复杂度为O(N2)。就是第一次选的 分界值使得左边一个没有，都在右边，
第二次也是，这样的话，会递归N层，每次都要进行（O(N)的遍历。

    void quick_sort(vector<int>&q,int l,int r)
    {
        if(l>=r) return;
        int t=q[l+r>>1];
        int i=l-1,j=r+1;
        while(i<j)
        {
            do(i++);while(q[i]<t);
            do(j--);while(q[j]>t);
            if(i<j)swap(q[i],q[j]);
        }
        quick_sort(q,l,j);
        quick_sort(q,j+1,r);
    }

7 堆排序
基于完全二叉树的数据结构。完全二叉树是指只有最后一层可以是不饱满的，
而且根节点的值是大（小）于左右儿子。
不稳定排序

void push_down(vector<int>&heap,int size,int u)
{
    int t=u,l=u*2,r=u*2+1;
    if(l<size&&heap[l]>heap[t])t=l;
    if(r<size &&heap[r]>heap[t])t=r;
    if(t!=u)
    {
        swap(heap[t],heap[u]);
        push_down(heap,size,t);
    }
}

void push_up(vector<int>&heap,int  u)
{
    while(u/2&&heap[u/2]<heap[u])
    {
        swap(heap[u/2],heap[u]);
        u/=2;
    }
}

void insert(vector<int>&heap,size,int x)
{
    heap[++size]=x;
    push_up(heap,size,x);
}


void remove_head(vector<int>&heap,size,int u)
{
    heap[1]=heap[size];
    size--;
    push_down(heap,size,1);
}

void heap_sort(vector<int>&q,int n)
{
    int size=n;
    //首先建堆
    for(int i=1;i<=n;i++) push_up(q,i);

    for(int i=1;i<=n;i++)
    {
        swap(q[1],q[size]);
        size--;
        push_down(q,size,1);
    }
}

8 计数代码（线性时间复杂度，前提是数据范围与数的个数大致相同，比如10e7个数，每个数的范围为0-10e7）

    void count_sort(vector<int>&q,int n)
    {//注意，我们这里q的下标是从1开始算起的
        vector<int>cnt(101,0);//计数数组，假设数的范围为0-100
        for(int i=1;i<=n;i++) cnt[q[i]]++;

        for(int i=1,k=1;i<=100;i++)
        {
            while(cnt[i])
            {
                q[k++]=i;
                cnt[i]--;
            }
        }
    }

9.桶排序：反应了一种思想，计数排序的升级
比如说数很多，0-20亿数据，那么我们可以搞个1000个，那么每个桶里面的数就有2000000个数
那么 【0，1999999】【2000000，3999999】。。。
那么桶内部的就可以使用任何的排序方式。
10.基数排序：按各个位进行排序。先将每个数按照每个位上的数放入，这样我们只需要10个桶，然后再将桶中的数
写回原数组，这样将所有的位数遍历完，数组就排好序了。

int get(int x,int i){//取出第i位的数
    while(i--) x/=10;
    return x%=10;
}

void radix_sort(vector<int>&q,int n)
{
    vector<vector<int>>cnt(10);//定义10个桶
    for(int i=0;i<3;i++)//循环3位
    {
        for(int j=0;j<10;j++) cnt[j].clear();//将桶清空

        for(int j=1;j<=n;j++){//处理所有的数，将数按照位数放进桶中
            cnt[get(q[j],i)].push_back(q[j]);
        }

        for(int j=0,k=1;j<10;j++){//再将桶中的数在重新写回原数组
            for(int x:cnt[j]){
                q[k++]=x;
        }
    }


}