|
算法分析 快速排序的时间主要耗费在划分操作上对长度为k的区间进行划分共需k次关键字的比较 ()最坏时间复杂度 最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录划分的结果是基准左边的子区间为空(或右边的子 区间为空)而划分所得的另一个非空的子区间中记录数目仅仅比划分前的无序区中记录个数减少一个 因此快速排序必须做n次划分第i次划分开始时区间长度为ni+所需的比较次数为ni(≤i≤n)故总的比较次数达 到最大值 C max = n(n)/=O(n ) 如果按上面给出的划分算法每次取当前无序区的第个记录为基准那么当文件的记录已按递增序(或递减序)排列时每次划分 所取的基准就是当前无序区中关键字最小(或最大)的记录则快速排序所需的比较次数反而最多 () 最好时间复杂度 在最好情况下每次划分所取的基准都是当前无序区的中值记录划分的结果是基准的左右两个无序子区间的长度大致相等 总的关键字比较次数 (nlgn) 注意 用递归树来分析最好情况下的比较次数更简单因为每次划分后左右子区间长度大致相等故递归树的高度为O(lgn)而递归 树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n故整个排序过程所需要的关键字比较总次数 C(n)=O(nlgn) 因为快速排序的记录移动次数不大于比较的次数所以快速排序的最坏时间复杂度应为(n )最好时间复杂度为O(nlgn) ()基准关键字的选取 在当前无序区中选取划分的基准关键字是决定算法性能的关键 ①三者取中的规则 三者取中规则即在当前区间里将该区间首尾和中间位置上的关键字比较取三者之中值所对应的记录作为基准在划分 开始前将该基准记录和该区伺的第个记录进行交换此后的划分过程与上面所给的Partition算法完全相同 ②取位于low和high之间的随机数k(low≤k≤high)用R[k]作为基准 选取基准最好的方法是用一个随机函数产生一个取位于low和high之间的随机数k(low≤k≤high)用R[k]作为基准这相当于 强迫R[lowhigh]中的记录是随机分布的用此方法所得到的快速排序一般称为随机的快速排序具体算法【参见教材】 注意 随机化的快速排序与一般的快速排序算法差别很小但随机化后算法的性能大大地提高了尤其是对初始有序的文件一般不 可能导致最坏情况的发生算法的随机化不仅仅适用于快速排序也适用于其它需要数据随机分布的算法 ()平均时间复杂度 尽管快速排序的最坏时间为O(n )但就平均性能而言它是基于关键字比较的内部排序算法中速度最快者快速排序亦因此 而得名它的平均时间复杂度为O(nlgn) ()空间复杂度 快速排序在系统内部需要一个栈来实现递归若每次划分较为均匀则其递归树的高度为O(lgn)故递归后需栈空间为O(lgn) 最坏情况下递归树的高度为O(n)所需的栈空间为O(n) ()稳定性 快速排序是非稳定的例如[ ] |
