快速排序问题请教

来源：百度知道编辑：UC知道时间：2024/05/27 09:09:26

怎么理解:
在一趟排序之后比较分割所得得两部分的长度，且先对长度短的子序列中的记录进行快速排序，则栈的最大深度可降为O（logn）?
补充:我觉得不论先对长度短的子序列中的记录进行快速排序,还是对长度长的子序列中的记录进行快速排序都是一样的.
而且栈的深度只有在长短差不多的时候才会是O（logn)

大家知道，递归对性能是有一定影响的，QSort函数在其尾部有两次递归操作。如果待排序的序列划分极端不平衡，递归深度将趋近于n，而不是平衡时的log2n，这就不仅仅是速度快慢的问题了。栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。因此如果能减少递归，将会大大提高性能。
于是我们对QSort实施尾递归优化。来看代码。
/* 对顺序表L中的子序列L.r[low..high]作快速排序 */
void QSort1（SqList *L,int low,int high）
{ int pivot;
if（（high-low）>MAX_LENGTH_INSERT_SORT）
{
while（low<high）
{
pivot=Partition1（L,low,high）; /*L.r[low..high]一分为二,*/ /*算出枢轴值pivot */ QSort1（L,low,pivot-1）; /* 对低子表递归排序 */ low=pivot+1; /* 尾递归 */ }
}
else InsertSort（L）;
}

当我们将if改成while后，因为第一次递归以后，变量low就没有用处了，所以可以将pivot+1赋值给low，再循环后，来一次Partition（L,low,high），其效果等同于“QSort（L,pivot+1,high）;”。结果相同，但因采用迭代而不是递归的方法可以缩减堆度而高体能栈深，从提高了整体性能。

I think you are right.
快排理论复杂度本来就是O(n^2)的
你哪里看的扯蛋书

快速排序问题请教快速排序的问题请教高手 “快速排序”的问题快速排序问题．快速排序的一个问题 C++快速排序的问题请教EXCEL排序问题请教VB排序问题请教排序小问题请教excel排序问题