题目

采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是()。

错因

A

快速排序的递归次数与初始数据的排列次序高度相关。当初始序列有序（或逆序）时，每次划分极度不均衡，退化为 O(n²) 次递归调用；随机数据下接近 O(n log n) 次。A 把"递归调用总次数"和"每次划分均衡度"的关系搞反了。

B

把"最大栈深度"与"总递归次数"混淆。先处理较长分区会让调用栈先往深处走，但两侧分区无论先后都必须处理，总的递归调用次数不变。B 的说法"减少递归次数"是错的。

C

类似 B，先处理较短分区确实是一种优化——能降低最大递归栈深（平均 O(log n)），避免栈溢出。但这只影响栈的最大深度，不影响递归调用的总次数。C 把"减少栈深"误表述为"减少递归次数"。

总解析

快速排序每次 partition 将数组一分为二后，左右两个子数组都必须处理。无论先处理左侧还是右侧，两边的递归调用都会发生，总调用次数由划分结果唯一决定，与处理顺序无关。

A 错：总次数与初始排列密切相关（最坏 O(n²)，最好 O(n log n)）。

B、C 错：先长或先短只影响调用栈的最大深度：

• 先短分区：每次把短的处理掉，最大栈深 O(log n)（优化策略，可防栈溢出）；
• 先长分区：最大栈深可能达 O(n)；
• 但两种策略下，总递归次数完全相同。

D 正确：递归次数与分区处理顺序无关。

最终答案是 D。