网页
资讯
视频
图片
知道
文库
贴吧
地图
采购
进入贴吧
全吧搜索
吧内搜索
搜贴
搜人
进吧
搜标签
日
一
二
三
四
五
六
签到排名:今日本吧第
个签到,
本吧因你更精彩,明天继续来努力!
本吧签到人数:0
一键签到
成为超级会员,使用一键签到
一键签到
本月漏签
0
次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行
补签
。
连续签到:
天 累计签到:
天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
10月07日
漏签
0
天
noip吧
关注:
25,166
贴子:
642,297
看贴
图片
吧主推荐
视频
游戏
11
回复贴,共
1
页
<<返回noip吧
>0< 加载中...
快排的最坏情况指什么?
只看楼主
收藏
回复
774255858
普及一等
4
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
Boolean93
怒进省队
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
就是被卡了,退化成n^2
Delostik
NOI铜牌
10
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
拍有序序列
除了诱惑都抵挡
提高二等
6
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
退化成冒泡。解决办法,简单点的就是mid:=a[random(r-l)+l].
し冷丶心ゾ
提高二等
6
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
排序从小到大的时候
如果遇见 100 99 98 97 ... 5 4 3 2 1这样的就是最坏的了
复杂度基本同冒泡
将不死还有爆栈风险
wangdebao2008
省选酱油
8
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
5l+1
Ac_Bug
提高二等
6
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
有序就悲剧了
Vic_Minty
提高一等
7
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
最坏情况是变量名打错了…
亟隐
省选酱油
8
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
用这个mid:=a[random(r-l)+l]听说会更卡,到底怎么回事……
Alison_Destiny
怒进省队
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
到底怎么回事啊= =决赛前能不能不要这么乱
chenrui9551
省选酱油
8
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
倒序的时候
while a[i]<a[mid] do inc(i) i不变,同理尾指针也没变
这样i=1,j=n,交换正好100在最后,1在最前面,一遍就有序了。。。
ymfoi
提高三等
5
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
快排的复杂度是期望O(nlogn)的,也就是平均情况下每次选取的基准值能把序列分成大小相近的两份,但是如果输入数据是一已经有序的数据,那么每次分治就分得极为不平均(每次分出1 和 n- 1两块),递归的深度不是O(logn)而是O(n)所以总复杂度就囧了。一个靠谱的办法是排序前先把数据再进行随机乱序,就很难被卡了。用std::sort是王道。
登录百度账号
扫二维码下载贴吧客户端
下载贴吧APP
看高清直播、视频!
贴吧页面意见反馈
违规贴吧举报反馈通道
贴吧违规信息处理公示