我现在在学校学习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
但令我惊讶的是，当程序在public static void display之前到达最后一个括号时，程序会跳回第 40 行if(i < right)但是突然间，right、i、j和pivot的值分别从5、2、-1和3变为、和。
如果有人能解释为什么价值观会改变，我将不胜感激。
我还添加了两张图片，它们显示了我在 Eclipse 窗口步骤中看到的内容，我不明白
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("nnleft = " + 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现在false （ 2 > 1 ）。
第一个条件left < j（0 < 1）是true，所以你再次递归地调用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 。第一个条件left < j也是false的（因为0 > -1），第二个条件i < right也是假的（因为1 == 1）所以这个调用结束了，你回到原来的位置。是吗？上表的第一个条件。变量和参数的状态现在为：
arr left right i j pivot
----------------- ------- -------- ------- ----- ----------
[10,5,3,22,11,2] 0 5 2 1 3
检查第二个条件（因为它是执行的下一行）。它的值也为真，因为条件是i < right（2 < 5）。所以你现在再次递归地quicksort：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
i > j现在，所以我们退出 while 循环。
第一个条件left < j（2 < 4）是true，所以我们调用quicksort(arr, 2, 4)以便对已经排序[5,10,11]进行排序。我将跳过这部分，因为它根本不会改变数组。
当递归调用完成后，我们返回到原来的位置，现在将检查第二个条件。 i < right（5 < 5）是false 所以我们完成了。
原始quicksort调用已完成，数组已排序。
您的第一张图片显示调试器位于快速排序的两个递归调用中：从 main 调用快速排序，然后在第 38 行再次调用快速排序（这是快速排序的原则，它是一种递归策略）。因此，您会看到您位于内部调用的第 40 行，然后当您从那里单步执行时，您返回到之前的快速排序调用（调试器在左上角窗口中显示两行而不是三行的堆栈），然后您返回到以前的透视值，等等。数组按原样传递给所有递归调用，因此它是共享的，但整数变量不是。
我认为这里是递归使它难以理解，请检查您的调用堆栈。
您使用 print 语句和调试器研究排序算法的努力值得称赞！但是你目前的 Quicksort 实现相当难以理解，至少在最初是这样，因为它同时进行了迭代和递归（即你使用循环，同时，你有一个过程quicksort调用自己）。
让我们采用一种相当不同的方法（纯递归方法）来了解快速排序的工作原理以及它的工作原理。幸运的是，将此递归过程转换为迭代过程（有点像您编写的）是一个技术问题（在这种情况下）！我建议我们在这里这样做，因为这样我们可以更好地控制复杂性。同样，我这样做的原因是为了更好地了解正在发生的事情。
当Tony Hoare爵士提出算法并证明其正确性时，它是这样的：
public static void qsort(int[] ints, int fi, int li) {
/* the recursive procedure */
if (fi < li) {
int p = partition(ints, fi, li); // key routine -- see below
qsort(ints, fi, p - 1);
qsort(ints, p + 1, li);
}
}
就是这样！不是很漂亮吗？嗯，是的。您要做的就是：
- 对给定的阵列进行分区。在我看来，分区是解决棘手问题的优雅过程。问题很简单：给定一个数字数组，重新排列数组，使其中有一个数字，其左侧的所有数字都小于或等于它，其右侧的所有数字都大于或等于它 - 返回数组中此类元素的索引。我敦促你尝试自己解决这个问题。维基百科上给出的两个程序（Lomuto和Hoare）都运行良好。
- 一旦确定分区按预期工作，就可以使用相同的
qsort过程递归地对两个分区进行排序（递归调用的顺序无关紧要），然后就完成了！
我尝试自己实现partition程序：
/**
Implements partitioning of array a from a[p] to a[r], leaves all the other elements of the array intact.
@param a the given int array
@param p int first index of the part of array to be partitioned
@param r int the second index of the part of array to be partitioned
*/
public static int partition(int[] a, int p, int r) {
//this is something I have written
int pivot = a[p];
int i = p + 1;
int j = i - 1;
while (i <= r) {
if (a[i] < pivot) {
a[j] = a[i];
a[i] = a[j+1];
j++;
}
i++;
}
a[j] = pivot;
return j;
}
private static void swap(int[] ints, int i1, int i2) {
int tmp = ints[i2];
ints[i2] = ints[i1];
ints[i1] = tmp;
}
现在，我还没有证明这个过程的正确性，但我们可以分开做。您甚至可以重新实现Lomuto过程，并看到它的工作令您满意。
仅此而已。如果您现在想使用调试器进行调试，那么您完全有能力做到这一点。这是整个实现。
现在，将这个递归过程转换为迭代过程的问题非常有趣，这个文档：（无耻的插件：我写的）http://bit.ly/recurse-iterate 应该给你一些线索。将上述快速排序过程实际转换为迭代过程留给读者作为练习：-）。