C++实现数组随机洗牌后快速排序出现段错误,求bug排查
问题原因
核心bug位于Partition函数的遍历边界设置错误:
- 你使用的Lomuto快速排序分区逻辑,在将数组末尾元素作为基准值(pivot)后,仅需要遍历下标范围为
s到e-1的元素,不需要遍历作为基准值的下标e的元素。 - 现有代码设置循环条件为
j <= e,会将基准值本身纳入遍历判断:arr[e] <= pivot必然成立,会导致变量i额外多累加1。后续执行swap(&arr[i + 1], &arr[e])操作时,i+1最大可达到e+1,直接触发数组越界访问,这是导致段错误的直接原因。
修复方案
将Partition函数中的for循环条件修改为仅遍历到e-1即可:
// 原错误代码:for (j = s; j <= e; j++) // 修改为 for (j = s; j < e; j++)
额外优化建议
你当前将srand(time(NULL))放在randomise函数内部,如果后续多次调用randomise,同一秒内的调用会使用相同的随机种子,得到完全一致的洗牌结果。建议将srand(time(NULL))移到main函数开头,全局仅执行一次即可。
内容的提问来源于stack exchange,提问作者loveofprogramming
相关产品推荐
相关产品推荐

