快速排序是运用了分治思想的排序方式,具有O(NlogN)的平均时间复杂度,极端情况下时间复杂度为O(N^2),跟冒泡排序一样,但是快排的实际效率远比最坏情况好很多。它的关键部分是一轮划分(由Partition()函数完成),每一轮划分会导致序列中的元素分成两部分,一部分比参照数小,一部分比参照数大。函数QSort()通过不断调用Partition()完成给定序列的排序,当排序序列细化为1个元素时,排序也就完成了,因为单个元素是有序的。
算法描述如下:


上面的Partition()存在很有必要优化的地方
我们先来看几个例子:
如果执行Partition()前的序列是:
10 5 6 3 2 7
用第一个元素做参照(上面说的t),我们发现后面所有的元素都小于t,因此i后一直向后找,直到找到最后一个元素;而j一次就找到了<= t 的元素,也就是最后一个元素。这样,while(1)结束了,Partition()执行之后,原序列变成:
5 6 3 2 7 10
如果执行Partition()前的序列是:
10 14 15 16 20
用第一个元素做参照(上面说的t),我们发现后面所有的元素都大于t,因此i一次就找到了 >= t的元素;而j一直向前找,直到找到第一个元素;这样,while(1)结束了,Partition()执行之后,原序列不变,仍然是:
10 14 15 16 20
上面这两种情况都是我们不愿看到的,因为它导致Partition()执行后,两边的元素很不平均,极端情况下(比如,原序列是已排好序的),快排的时间复杂度是O(N^2),跟冒泡排序一样。为了避免这种情况出现,我们可以采用随机化的策略,即不老是选择第一个元素做参照,为达到这一目的,可以提前将后面的任意一个元素与第一个元素交换。
优化后的算法为:


接下来我们在快速排序中划分函数Partition()的基础上讲解一下线性时间选择问题。所谓线性时间就是在平均O(N)的时间内找出无序序列中第k大的元素。先排序再找出该元素是比较容易想到的方法,但排序所花的时间很可能超过O(N)(比如,快排、堆排的时间复杂度都是O(NlogN),选择排序、插入排序以及冒泡排序时间复杂度是O(N^2))。
其实结合Partition()函数完成的一次划分我们很容易想到,选择第k大的元素不一定要排序原序列,因为经过一次划分,原序列以参照数t为基准被分成了两部分,我们要找的第k大的数要么就是t,要么在t左边,要么在t右边,因此每次迭代我们只需要考虑原序列接近1/2的数字就行了。显然,Select()函数的效率跟Partition()的好坏有直接关系,最坏情况下,Select()函数的时间复杂度仍为O(N^2)。
算法描述如下:
上面两种描述略有不同,前面是我写的,后面一个是书上的。这两种算法都忽略了一个问题,那就是没有考虑非法情况,即要选择的数超出了原有序列,比如原序列只有n个数,而却让找出第n+1大的数。 
posted on 2012-07-17 16:46 小鼠标 阅读(3615) 评论(1)  编辑 收藏 引用 所属分类: 排序

FeedBack:
# re: 快速排序、线性时间选择
2012-10-17 10:05 | lsxqw2004
博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜