任何人都可以明白为什么这个排序递归示例在第二次调用递归方法后继续运行。当i == high_index
他们都在哪里2
由于某种原因第二次调用后,我在互联网上发现的这段代码再次运行同一行,但有一些奇怪的值 i=4
和high_index=6
。我只是看不到这个错误。所有递归都应该在第二次之后停止,并且应该对数组进行排序。
参见带有注释的行 //WHY DOES THIS LINE RUN TWICE IN A ROW WITH DIFFERENT VALUES?????
package dataClass;
import java.util.Arrays;
public class QuickSort {
private int temp_array[];
private int len;
public void sort(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
this.temp_array = nums;
len = nums.length;
quickSort(0, len - 1, "First");
//System.out.println("what");
}
private void quickSort(int low_index, int high_index, String one_two) {
System.out.println("***" + low_index + " " + high_index);
System.out.println(one_two);
int i = low_index;
int j = high_index;
// calculate pivot number
int pivot = temp_array[low_index+(high_index-low_index)/2];
// Divide into two arrays
System.out.println(Arrays.toString(temp_array));
while (i <= j) {
while (temp_array[i] < pivot) {
System.out.println("This happens");
i++;
}
while (temp_array[j] > pivot) {
System.out.println("Or this happens");
j--;
}
if (i <= j) {
System.out.println("Execute");
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
System.out.println("i=" + i + " high_index=" + high_index);
}
}
// call quickSort() method recursively
if (low_index < j) {
System.out.println("Running 1");
System.out.println(j + " " + low_index);
quickSort(low_index, j, "Run 1---------");
}
System.out.println("**i=" + i + " **high_index=" + high_index); // WHY DOES THIS LINE RUN TWICE IN A ROW WITH DIFFERENT VALUES?????
System.out.println("Why run again without call to quickSort()?");
if (i < high_index) {
System.out.println("Running 2");
System.out.println(i + " " + high_index);
quickSort(i, high_index, "Run 2---------");
}
}
private void exchangeNumbers(int i, int j) {
int temp = temp_array[i];
temp_array[i] = temp_array[j];
temp_array[j] = temp;
}
// Method to test above
public static void main(String args[])
{
QuickSort ob = new QuickSort();
int nums[] = {7, -5, 3, 2, 1, 0, 45};
System.out.println("Original Array:");
System.out.println(Arrays.toString(nums));
ob.sort(nums);
System.out.println("Sorted Array");
System.out.println(Arrays.toString(nums));
}
}
最佳答案
虽然我没有真正追踪这里的完整逻辑,但我相信缺少“return”语句。当控制权到达递归方法调用调用时,该方法将再次执行。但是,一旦递归调用执行完成,原始方法调用的执行就会恢复,您会看到意外的行为!
在进行递归调用时也在其他地方返回(中断执行流程),以防止进一步按预期执行代码块
if (low_index < j) {
System.out.println("Running 1");
System.out.println(j + " " + low_index);
quickSort(low_index, j, "Run 1---------");
//recursive code invoked, but prevent the control to process downstream code
return;
}
关于java - 递归循环再次运行,无需在 Java 中调用它,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56511898/