快速排序问题请教
发布网友
共2个回答
热心网友
大家知道，递归对性能是有一定影响的，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)的
你哪里看的扯蛋书
