(排序)P1177 【模板】快速排序
2024-10-08 18:25:29
题解:
这道题用传统快排(如下所示)的结果就是最后三个点TLE:
如果永远取第一个元素作为枢轴的话,在数组已经有序的情况下每次划分都将得到最坏的结果,时间复杂度退化为O(n^2)。因为其中一个子序列每次都只比原序列少一个元素,该侧的递归深度将达到最大。
#include<iostream>
using namespace std;
int n,a[1000001];
void swap(int &a,int &b){
int t=a;
a=b;
b=t;
}
void qsort(int l,int r)//应用二分思想
{
int mid=a[(l+r)/2];//中间数
int i=l,j=r;
do{
while(a[i]<mid) i++;//查找左半部分比中间数大的数
while(a[j]>mid) j--;//查找右半部分比中间数小的数
if(i<=j)//如果有一组不满足排序条件(左小右大)的数
{
swap(a[i],a[j]);//交换
i++;
j--;
}
}while(i<=j);//这里注意要有=
if(l<j) qsort(l,j);//递归搜索左半部分
if(i<r) qsort(i,r);//递归搜索右半部分
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
qsort(1,n);
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}
最新文章
- i++ and ++i efficiency
- C++ 文件读取
- [转]Javascript定义类的三种方法
- poj magic number
- Ajax的基本请求/响应模型
- p便签,去掉首行缩进
- Linux防火墙配置—SNAT2
- 移动端touch事件封装
- .Neter玩转Linux系列之二:Linux下的文件目录及文件目录的权限
- 如何用CropBox实现头像裁剪并与java后台交互
- 使用dlib中的深度残差网络(ResNet)实现实时人脸识别
- Navicat Premium 12.1.16.0安装与激活
- BZOJ 4196 软件包管理器
- Confluence 6 启用远程 API
- 七牛云存储 qiniu 域名 回收 文件上传 备份 下载 MD
- Java使用Log4记录日志
- bat计算两个时间差
- TP5常量
- Java何时该使用覆盖?
- C - A Plug for UNIX (又是建图坑)