我现在在学校学习Java,我们最新的主题是Java中的排序算法.我想要了解的是快速排序.
为了理解该算法如何对数组中的数字进行排序,我决定在Eclipse调试器窗口中执行我的代码步骤.
现在有一个步骤,即使经历了数百次之后我也无法理解.
我的初始数组是[10,5,3,22,11,2]
当我浏览代码时,程序首先交换10和2,然后是5和3,然后是2和2.此时,i的值为1,j的值为-1.
现在我看到它的方式是有三个条件
> while(i< = j)返回false,因为i = 1且j = -1
> if(left< j)返回false,因为left = 0且j = -1
> if(i< right)其中也返回false,因为i = 1且right = 1
但令我惊讶的是,当程序在公共静态无效显示之前到达最后一个括号时,如果(i <右),程序将跳回到第40行.
但突然,右,i,j和枢轴的值分别从5,2,-1和3变为.
如果有人能解释为什么值会发生变化,我将非常感激.
我还添加了两张图片,显示了我在Eclipse窗口step I don’t understand上看到的内容
public class QSort {
public static void quickSort(int[] arr, int left, int right){
int i = left;
int j = right;
int temp;
int pivot = arr[(left+right)/2];
System.out.println("\n\nleft = " + left + "\tright = " + right);
System.out.println("Pivot is: " + pivot + "(" + (left+right)/2 + ")");
while(i <= j){
while(arr[i] < pivot){
System.out.println("i is: " + arr[i] + "(" + i + ")");
i++;
System.out.println("i is: " + arr[i] + "(" + i + ")");
}
while(arr[j] > pivot){
System.out.println("j is: "+ arr[j] + "(" + j + ")");
j--;
System.out.println("j is: "+ arr[j] + "(" + j + ")");
}
if(i <= j){
System.out.println("i is: " + arr[i] + "(" + i + ")");
System.out.println("j is: "+ arr[j] + "(" + j + ")");
System.out.println("Swapped " + arr[i] + "(" + i + ")"+ " with " + arr[j] + "(" + j + ")");
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
System.out.println("i is: (" + i + ")");
System.out.println("j is: (" + j + ")");
System.out.println("Pivot is: " + pivot + "(" + (left+right)/2 + ")");
}
}
if(left < j){
System.out.println("j is: (" + j + ")");
quickSort(arr, left, j);
}
if(i < right){
System.out.println("i is: (" + i + ")");
quickSort(arr, i, right);
}
}
public static void display(int[] arr){
if(arr.length > 0){
System.out.print(arr[0]);
}
for(int i = 1; i < arr.length; i++){
System.out.print(", " + arr[i]);
}
}
public static void main(String[] args) {
int[] data = new int[]{10,5,3,22,11,2};
System.out.println("Before: ");
display(data);
quickSort(data, 0, data.length-1);
System.out.println("\nAfter: ");
display(data);
}
}
非常感谢！
解决方法:
我认为你的问题是你不完全理解递归.至少从你对这个问题的描述中听起来就是这样.
无论如何,我试图通过记录所有变量来简单地遵循你的程序.希望这可以帮助：
arr left right i j pivot
----------------- ------- -------- ------- ----- ----------
[10,5,3,22,11,2] 0 5
0 5 arr[2] = 3
[2,5,3,22,11,10] 1 4
3
2
[2,3,5,22,11,10] 2 1
while循环结束,因为i< = j现在为假(2> 1). 第一个条件是< j(0 <1)为真,所以你再次递归调用quicksort：quicksort(arr,0,1) - 这意味着你现在对已经排序的数组[2,3]进行排序,所以不会发生任何事情：
arr left right i j pivot
----------------- ------- -------- ------- ----- ----------
[2,3,5,22,11,10] 0 1
0 1 arr[0] = 2
0
[2,3,5,22,11,10] 1 -1
while循环条件现在为false.第一个条件是< j也是假的(因为0> -1)并且第二个条件i <1.权利也是假的(因为1 == 1)所以这个电话结束了,你回到了原来的位置.是那样的吗？上表的第一个条件.变量和参数的状态现在是：
arr left right i j pivot
----------------- ------- -------- ------- ----- ----------
[10,5,3,22,11,2] 0 5 2 1 3
检查第二个条件(因为它是下一行执行).它的值也是正确的,因为条件是i <1.对(2 <5).所以你现在再次递归快速输入：quicksort(arr,2,5) - 这意味着你现在对数组[3,22,11,10]进行排序：
arr left right i j pivot
----------------- ------- -------- ------- ----- ----------
[2,3,5,22,11,10] 2 5
2 5 arr[3] = 22
3
[2,3,5,10,11,22] 4 4
5
我> j现在我们退出while循环.
第一个条件是< j(2 <4)为真,所以我们称为quicksort(arr,2,4)以便对已经排序的[5,10,11]进行排序.我将跳过这部分,因为它根本不会改变数组. 当递归调用完成后,我们返回到原来的状态,现在将检查第二个条件.我<对(5 <5)是假的所以我们已经完成了. 原始的快速排序调用已完成,数组已排序.