老师请帮忙看下,以下代码输出结果是否有问题,谢谢
# 具体遇到的问题
按照样例代码输出7个数字的特殊数组
# 报错信息的截图
输出结果不符合作业中描述的结果,比如1和2的位置
after infixOrder arr[0, 6]1 5 3 0 2 4 6
# 相关课程内容截图
生成数组:
// 生成一个长度为 n 的随机数组, 每个数字的范围是 [0, bound)
public static Integer[] generateSpecialArray(int n){
Integer[] arr = new Integer[n];
infixOrder(arr, 0, arr.length -1, 0, 0);
return arr;
}
public static void infixOrder(Integer[] arr, int l, int r, int value, int depth){
if(l > r) return;
// 生成深度字符串
String depthString = generateDepthString(depth);
// 打印当前 sort 处理的数组区间信息
System.out.print(depthString);
System.out.println(String.format("infixOrder arr[%d, %d]", l, r));
int mid = l + (r - l) / 2;
arr[mid] = value;
swap(arr, l, mid);
infixOrder(arr, l + 1, r, value + 1,depth + 1);
swap(arr, l, mid);
// 打印当前 sort 处理的数组区间信息
System.out.print(depthString);
System.out.print(String.format("after infixOrder arr[%d, %d]", l, r));
for(int i = l; i <= r; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
执行:
int n = 7;
arr = ArrayGenerator.generateSpecialArray(n);
打印输出:
after infixOrder arr[0, 6]1 5 3 0 2 4 6
# 尝试过的解决思路和结果
二叉树转数组也不对,请老师帮忙看下
# 粘贴全部相关代码,切记添加代码注释(请勿截图)
在这里输入代码,可通过选择【代码语言】突出显示
正在回答
抱歉,我没有特别理解你的问题。你的意思是,对于怎样的输入,你认为应该的输出结果是怎样的?你的算法实际的输出结果是怎样的?
==========
1 5 3 0 2 4 6 是正确的。
我们生成的测试用例,保证每次选择中间的元素做标定点,这个标定点是当前数组的最小值。
最初,选择 0 是标定点。经过第一轮 partition 以后,会变成 0 5 3 1 2 4 6,标定点 0 在最左边,之后处理 5 3 1 2 4 6,此时,中间的 1 依然是剩下未处理数组的最小值。
关键是,在快速排序的过程中, partition 会改变数组。我建议你使用这个生成的数组,实际运行快速排序(标定点选择中间值),运行试试看?再理解一下,我们为什么这么生成这个特殊的数组?
继续加油!:)
恭喜解决一个难题,获得1积分~
来为老师/同学的回答评分吧
0 星