基本排序算法及分析（四）：快速排序

     摘要: 快速排序:确定一个枢纽元，一次遍历后将数组划分成两个部分，第一部分均比枢纽元小，第二部分都比枢纽元大，然后对这两个数组进行快速排序，是一种递归的方法
平均运行时间O(Nlog(N)),最坏运行时间O(N^2)
最坏情形：对于预排序的序列。
对与枢纽元相等的元素处理：
i,j都停止：会比较相等元素，但是可以划分成长度相当的两个子数组
i,j都不停止，不会比较相等元素，但是可能产生长度不平衡的两个子数组(与枢纽元相等的元素较多时)枢纽元的选取：
1. 选取第一个元素做枢纽元：对于（部分）预排序的序列运行时间O(N^2)
2. 随机生成枢纽元：能避免上述问题，但是产生枢纽元的代价高
3. 三数中值分割法：选取左端，右端，中间位置三个元素的中值  阅读全文

幸运草 2009-04-22 16:56 发表评论