对n个元素的数组进行快速排序，所需要的额外空间为?
AO(1)
BO(n)
CO(logn)
DO(n^2))
答案是C解析：快速排序的一趟需要用到辅助变量，空间复杂度为O(1)，平均情况下递归树高度为O(logn)，故空间复杂度为O(logn)：最好情况是logn，最差情况是n，所以需要额外的辅助空间是o（logn）～o（n）。PS：以前我说错了，再次更正一下。
intPartition(intr[],intfirst,intend)
{
inti=first;
intj=end;//初始化
while(ij)
{
while(ijr[i]=r[j])j--;//右侧扫描
if(ij){
std::swap(r[i],r[j]);//i++;//将较小记录交换到前面
}
while(ijr[i]=r[j])i++;//左侧扫描
if(ij){
std::swap(r[i],r[j]);//j--;//将较大记录交换到后面
}
}
returni;
//i为轴值记录的最终位置
}
voidQuickSort(intr[],intfirst,intend)
{
if(first=end){
return;
}
intpivotpos=Partition(r,first,end);//一次划分
QuickSort(r,first,pivotpos-1);
//对前一个子序列进行快速排序
QuickSort(r,pivotpos+1,end);
//对后一个子序列进行快速排序
}
赞赏