HooLee
If you believe, you can!
C++博客
首页
新随笔
新文章
联系
管理
2012年7月17日
快速排序、线性时间选择
摘要: 快速排序是运用了分治思想的排序方式,具有O(NlogN)的平均时间复杂度,极端情况下时间复杂度为O(N^2),跟冒泡排序一样,但是快排的实际效率远比最坏情况好很多。它的关键部分是一轮选择(由Partition()函数完成)……所谓线性时间就是在平均O(N)的时间内找出无序序列中第k大的元素。它是以Partition()函数的划分为依据的……
阅读全文
posted @
2012-07-17 16:46
小鼠标 阅读(3615) |
评论 (1)
|
编辑
收藏
<
2012年7月
>
日
一
二
三
四
五
六
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
常用链接
我的随笔
我的评论
我参与的随笔
随笔分类
(111)
C语言(3)
DP(9)
Java笔记(1)
Java基础练习(25)
安卓(1)
本科毕设(1)
博弈(1)
大数(7)
回溯(2)
排序(10)
暑期培训周赛(3)
数据结构(7)
数论(1)
水题(8)
图论(24)
网选训练(8)
随笔档案
(127)
2014年3月 (1)
2013年7月 (10)
2013年5月 (1)
2013年4月 (11)
2013年3月 (8)
2012年10月 (1)
2012年9月 (12)
2012年8月 (38)
2012年7月 (14)
2012年6月 (2)
2012年5月 (8)
2012年4月 (6)
2012年3月 (6)
2012年2月 (4)
2011年8月 (5)
friends
陈钢
大鹏
党姐
焦林枫
汪涛
小白学长
媛姐
媛姐csdn
最新评论
1. re: 线段树
是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
加油,祝你好运啦!
--小鼠标
2. re: 线段树
对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
--伤心的笔
3. re: poj1273--网络流
过来看看你。
--achiberx
4. re: (转)ubuntu11.10无法启动无线网络的解决方法
膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
--Hang
5. re: 快速排序、线性时间选择
博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
--lsxqw2004
阅读排行榜
1. 单调队列(5479)
2. Linux select()函数使用(3952)
3. 快速排序、线性时间选择(3615)
4. poj3468--绝对经典的线段树题(3609)
5. 优先队列--堆实现(3291)