C++递归实现快速排序代码错误排查解答

题目要求 #

• 功能：递归实现快速排序，对输入数组做升序排列
• 输入规则：
  • 第一行输入整数n，为数组长度
  • 第二行输入n个空格分隔的整数，为数组元素
• 输出规则：输出空格分隔的升序排序后数组元素
• 约束：数组长度范围为 1 ≤ n ≤ 10^3

现有代码错误点 #

• 存在直接导致编译失败的语法错误
  代码开头残留了一段无效代码：两个空实现的quickSort重载函数，以及一个没有对应注释起始标记的*/注释结束符，编译器遇到这个孤立的*/会直接报语法错误，这部分内容需要完全删除。
• count函数的静态变量导致计数完全失效
  你在count函数里定义了静态局部变量c，静态变量的特点是程序运行期间只会初始化一次，不会在每次函数调用时重置为0。第一次调用count计算完第一个分区的计数后，后续递归处理左右子分区调用count时，c会在之前的累计值上继续累加，根本无法正确计算当前分区内的元素大小关系，直接导致后续计算的基准位置pi完全错误，甚至会出现数组下标越界的未定义行为。
  就算去掉静态变量，这个count函数的逻辑本身也不成立：你固定拿区间起始位置的元素和区间末尾向前遍历的元素比大小计数，根本统计不到区间内所有小于基准值的元素总数，算出来的位置根本不是基准值应该在的正确位置。
• 分区函数partionArray逻辑不成立
  快排分区的核心要求是：分区完成后基准值左侧所有元素都不大于基准值，右侧所有元素都不小于基准值。你写的循环条件while(i<pi&&j>pi)存在明显漏洞：只要左指针i走到基准位置、或者右指针j走到基准位置，循环就直接终止，完全没有处理指针越过基准位置的场景，会导致大量大于基准的元素留在左侧、小于基准的元素留在右侧，分区完全失效。
  另外你靠提前遍历计数找基准位置的写法，不仅容易出错，还会把快排的时间复杂度拉高到O(n²)，完全不符合快排的常规实现逻辑。
• 输出格式存在小问题
  你循环输出每个元素时固定在元素后加空格，最终输出的字符串末尾会多一个多余的空格，部分严格的判题系统会直接判定格式错误。

整体逻辑判断 #

你的代码递归分治的大框架是对的：找到分区点、递归处理左右子区间的结构没有问题，但核心的基准选择、分区实现、计数逻辑都存在致命错误，绝大多数测试用例都无法输出正确的排序结果，无法通过题目判题。

内容的提问来源于stack exchange，提问作者Saketh REddy