快速算法的性能 据结构 平均时间性能:O(n*ogn),最坏为On*n) 空间复杂度: 最坏情况,栈的最大深度n 最好情况,栈的最大深度Logn」+1 通过改进算法可以改善空间复杂度:在一趟 内部排序 排序之后比较分割所得两部分的长度,且先对长 度短的子序列中的记录进行快速排序,则栈的最 大深度可降为O(logn) >快速排序方法是不稳定的。 用队列实现快排的非递归算法 QuickSort Q(sqlist &lt ∥建立一个足够大的循环队列∥ InitQ(Q); InQ(Q, 1); InQ(Q, Llength) while(empty(Q)t OutQ(Q, start); OutQ(Q, end )i iQuickOne(L, start, end); 内部排序 if(start<i-1) (InQ(Q, start); InQ(Q, 1-1); if(end >i+l) ((Q, i+1); InQ(Q, end): 1 3417 数 据 结 构 之 内 部 排 序 33 ¾ 快速算法的性能 ¾ 平均时间性能：O(n*log n)，最坏为 O(n*n) ¾ 空间复杂度： 最坏情况，栈的最大深度 n 最好情况，栈的最大深度 log n  + 1 通过改进算法可以改善空间复杂度：在一趟 排序之后比较分割所得两部分的长度，且先对长 度短的子序列中的记录进行快速排序，则栈的最 大深度可降为O( log n) ¾ 快速排序方法是不稳定的。 数 据 结 构 之 内 部 排 序 34 用队列实现快排的非递归算法 QuickSort_Q(SqList &L){ // 建立一个足够大的循环队列 // InitQ(Q) ; InQ(Q , 1) ; InQ(Q , L.length); while(!empty(Q)){ OutQ(Q , start); OutQ(Q , end ); i=QuickOne(L ,start , end ); if(start<i-1) { InQ(Q , start); InQ(Q , i-1 );} if(end >i+1) { InQ(Q , i+1) ; InQ(Q , end );} } }