【快速排序】

简介: 【快速排序】

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

快速排序算法通过多次比较和交换来实现排序,其排序流程如下:
(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;
}
相关文章
|
开发工具 Android开发 数据安全/隐私保护
搞机:AS自带模拟器AVD Root 和 Xposed安装(上)
AS自带模拟器AVD Root 和 Xposed安装
1508 0
|
存储 程序员 C++
C++程序局部变量:生命周期与作用域的探讨
C++程序局部变量:生命周期与作用域的探讨
339 1
|
8月前
|
SQL 存储 关系型数据库
PolarDB 开源基础教程系列 4 日常运维
PolarDB日常运维指南涵盖了多个关键操作,包括读写节点故障切换、增加只读节点、配置WAL日志归档、备份与恢复、创建容灾实例以及排查CPU负载高等。通过详细的步骤和代码示例,本文档帮助用户在本地环境中体验和学习PolarDB的高级功能,如共享存储架构下的集群管理。特别地,文档提供了如何使用`polar_basebackup`工具进行备份和恢复,确保数据安全;并通过`pg_stat_statements`插件定位慢查询,优化数据库性能。此外,还介绍了常见问题的排查方法,如业务量上涨或长时间执行的SQL语句导致的CPU高负载。更多内容和进阶课程可参考提供的GitHub链接和官方文档。
352 2
|
12月前
|
网络协议 安全 网络安全
IPv4 地址耗尽,为什么 IPv6 没有广泛将其取代?
IPv4 地址耗尽,为什么 IPv6 没有广泛将其取代?
367 0
|
12月前
|
移动开发 小程序 数据可视化
HBuilderX 小白上手指南
HBuilderX 小白上手指南
721 0
|
10月前
|
人工智能 前端开发 Serverless
解决方案评测:主动式智能导购AI助手构建
解决方案评测:主动式智能导购AI助手构建
248 3
|
11月前
|
SQL 关系型数据库 MySQL
MySQL性能探究:count(*)与count(1)的性能对决
在MySQL数据库的性能优化中,对查询语句的细微差别有着深入的理解是非常重要的。`count(*)`和`count(1)`是两种常用的聚合函数,用于计算行数。在面试中,面试官经常会问到这两种函数的性能差异。本文将探讨`count(*)`与`count(1)`的性能对比,并整理十道经典的MySQL面试题,帮助你在面试中游刃有余。
292 3
|
12月前
|
机器学习/深度学习 存储 人工智能
揭秘机器学习背后的神秘力量:如何高效收集数据,让AI更懂你?
【10月更文挑战第12天】在数据驱动的时代,机器学习广泛应用,从智能推荐到自动驾驶。本文以电商平台个性化推荐系统为例,探讨数据收集方法,包括明确数据需求、选择数据来源、编写代码自动化收集、数据清洗与预处理及特征工程,最终完成数据的训练集和测试集划分,为模型训练奠定基础。
287 3
|
12月前
|
SQL 存储 分布式计算
Hadoop-16-Hive HiveServer2 HS2 允许客户端远程执行HiveHQL HCatalog 集群规划 实机配置运行
Hadoop-16-Hive HiveServer2 HS2 允许客户端远程执行HiveHQL HCatalog 集群规划 实机配置运行
197 3
|
弹性计算 自然语言处理 负载均衡
部署高可用WordPress网站
高可用服务是另外一个高频使用的场景,编写模板的流程和《部署单点WordPress网站》一样,但涉及的资源更多一些。本文以《部署高可用WordPress网站》为例,介绍高可用部署类的模板如何编写。
81361 8