首先我们先回顾一下什么是快速排序？

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)利用分治的思想 首先设定一个分界值x，通过该分界值将数组分成左右两部分（若一开始左边<右边，则直接输出）。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
模拟快排代码如下：

void quick_sort(int q[],int l,int r)
{
   
if（l<r）return ;
int x=q[(l+r)>>1];
int i=l-1;
int j=r+1;
while（i<j)
{
   
do i++;
while( q[i]<q[x]);
do j--;
while(q{
   j}>q[x]);
if(i<j)swap(q[i],q[j]);
}
quick_sort(q,l,j);//排序左边
quick_sort(q,j+1,r);//排序右边
}

@[TOC]

题目：栗酱的连通图

链接：栗酱的连通图
来源：牛客网

题目描述
萌萌哒栗酱有n个点，第i个点有点权ai(ai为偶数)，你可以在任意两点之间添加一条边，每一条边的边权为连接它的两个点的点权之和除以2。
现在她需要添加n-1条边，使任意两点相互连通，并且连通后的边权和最大。
输入描述:
第一行一个数T，表示有T组数据。
对于每组数据，第一行输入一个数n，表示点的数量，
接下来一行输入n个数，a1,a2,…,an,其中ai表示第i个点的点权。
任意两个相邻数之间用空格隔开。
输出描述:
对于每一组数据，输出一个数，即最大边权和。
示例1
输入
2
5
4 2 4 4 2
10
10 2 6 4 6 8 10 8 2 10
输出
14
73
备注:
T≤10
1≤n≤103
1≤ai≤103，保证ai为偶数。

题解：
1.先进行排序
2.要使得边权和最大 则需要每数与最大数相连

代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t;
const int N=1e4+10; 
int q[N];
void my_sort(int q[],int l,int r)
{
   
    if(l>=r)return;
    int x=q[(l+r)>>1];
    int i=l-1;
    int j=r+1;
    while(i<j)
    {
   
        do i ++ ;while(q[i] < x);
        do j -- ;while(q[j] > x);
        if(i < j)
            swap(q[i],q[j]);
    }
    my_sort(q,l,j);
    my_sort(q,j+1,r);
}
int main()
{
   
    cin>>t;
    while(t--)
    {
   
        int n;
        int sum=0;
        cin>>n;
        for(int i=1;i<=n;i++) scanf("%d",&q[i]);
        my_sort(q,0,n);
        for(int i=1;i<n;i++)
            sum+=(q[i]+q[n])/2;//q[n]为最大数
        cout<<sum<<endl;
    }
}

题目：小杰的签到题

链接：小杰的签到题
来源：牛客网

题目描述
小杰组织了一场比赛，在比赛前需要安排队伍签到，但他不确定签到要花多久时间，现在他来请求你的帮助。已知签到是在一个体育馆，该体育馆布置有三个桌子以供不同队伍的队伍同时签到，一个桌子最多只能有一支队伍签到，一支队伍只需在一张桌子前完成签到即可。如果三个桌子都有队伍在签到，其它需要签到的队伍就需要在任意一个桌子前排队，等待签到。
我们假设在t=0的时刻开始接受签到，n支队伍分别在a1,a2,...,an时刻到达体育馆，每支队伍完成签到均需b的时间，为使问题简单，我们忽略体育馆中移动的时间。你需要告诉小杰最早什么时刻，所有的队伍均签到完成。
输入描述:
多组读入。
输入数据的第一行是一个整数T，表示数据的组数。
每组数据的第一行是一个整数n，表示签到的队伍数。
接下来一行有n个整数ai，表示第i支队抵达体育馆的时间。
每组的最后一行是一个整数b，表示一支队伍完成签到的时间。
输出描述:
对于每组数据，输出最后一支队伍最早签到完成的时刻。
示例1
输入
2
5
1 2 4 5 7
4
7
4 4 4 2 8 9 11
5
输出
11
17
备注:
1≤n≤600
0≤ai≤104
1≤b≤1500
数据不超过250组

题解：
1。按到达时间排序
2.若小于三支队伍则，时间为最后一个队伍+b
3.若大于三支队伍，则第n个与n-3个进行比较，若n的到达时间>n-3的到达时间+b(签到时间)则最终时间为n的到达时间+b,否则时间为(n-3的到达时间+b)+b.

代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int T;
const int N= 1e4+10;
int q[N];
void my_sort(int q[],int l,int r)
{
   
    if(l>=r)return;
    int x=q[(l+r)>>1];
    int i=l-1;
    int j=r+1;
    while(i<j)
    {
   
        do i ++ ;while(q[i] < x);
        do j -- ;while(q[j] > x);
        if(i < j)
            swap(q[i],q[j]);
    }
    my_sort(q,l,j);
    my_sort(q,j+1,r);
}
int main()
{
   
    cin>>T; int n;int b;
    while(T--)
    {
    
        cin>>n;
        for(int i=0;i<n;i++)cin>>q[i];
           cin>>b;
           my_sort(q,0,n);
     if (n <= 3) printf("%d\n", q[n - 1] + b); //小于三支队伍
        else{
   
            q[0] += b;
            q[1] += b;
            q[2] += b;
            int temp = 0;
            for (int i = 3; i < n; i ++ )
            {
   
                temp = max(q[i], q[i - 3]);//max：q[i - 3]大：无等待时间+签到时间
                q[i] = temp + b;//q[i]大：等待时间+签到时间
            }
            printf("%d\n", q[n - 1]);
           }
    }
return 0;
}

题目：过来站站队伍

链接：过来站站队伍
来源：牛客网

题目描述
在某个星球，每个人身上都有不一样的标号。一天，小娟在食堂排队时，发现后面老是喜欢插队，她看到很生气，拿出一张魔法卡，巴拉巴拉能量（魔仙变身，看多了动画片，hhh）。。。。。。。，将他们全部按照从小到大按照标号排好了。你能帮忙写出魔法卡内部的程序吗？写出来就给你一个气球。嘿嘿嘿
输入描述:
第一行，输入一个整数n(1<=n<=100000);
第二行，输出n个整数；
注意多组输入
输出描述:
输出n个数
示例1
输入
3
1 3 2
输出
1 2 3
示例2
输入
5
1 3 4 2 5
输出
1 2 3 4 5

题解：

1。排序即可

代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
const int N=1e5+10;
int q[N];
void my_sort(int q[],int l,int r)
{
   
    if(l>=r)return;
    int x=q[(l+r)>>1];
    int i=l-1;
    int j=r+1;
    while(i<j)
    {
   
        do i ++ ;while(q[i] < x);
        do j -- ;while(q[j] > x);
        if(i < j)
            swap(q[i],q[j]);
    }
    my_sort(q,l,j);
    my_sort(q,j+1,r);
}
int main()
{
   
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        cin>>q[i];
        my_sort(q,0,n);
   // sort(q,q+n);
    for(int i=0;i<n;i++)
        cout<<q[i]<<' ';

    return 0;
}

题目：别看了 这是水题

链接：别看了这是水题
来源：牛客网

题目描述
把一个长度为N的数值数组按从小到大的顺序排序并输出
输入描述:
输入为两行 第一行为一个整型数字N 第二行输入N个整型数字num 代表数组里面的元素（每个元素之间用空格隔开）
输出描述:
输出为一行 即为数组从小到大排序后的结果 每个数字之间用空格隔开（行末没有空格）
示例1
输入
5
2 8 7 4 5
输出
2 4 5 7 8
示例2
输入
4
2 2 2 2
输出
2 2 2 2
备注:
0<N<1000
0<num<=10000

题解：
1.排序即可

代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e4 + 10;
int n;
int q[N];
 void my_sort(int q[],int l,int r)
{
   
    if(l>=r)return;
    int x=q[(l+r)>>1];
    int i=l-1;
    int j=r+1;
    while(i<j)
    {
   
        do i ++ ;while(q[i] < x);
        do j -- ;while(q[j] > x);
        if(i < j)
            swap(q[i],q[j]);
    }
    my_sort(q,l,j);
    my_sort(q,j+1,r);
}
int main()
{
   
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) 
        cin >> q[i];
        my_sort(q,0,n);
    //sort(q, q + n);
    for (int i = 0; i < n; i ++ ) 
        cout << q[i] << ' ';
    return 0;
}