Java Quicksort值为什么/在哪里变化？

Question

我现在在学校学习Java,我们最新的主题是Java中的排序算法.我想要了解的是快速排序.

为了理解该算法如何对数组中的数字进行排序,我决定在Eclipse调试器窗口中执行我的代码步骤.

现在有一个步骤,即使经历了数百次之后我也无法理解.

我的初始数组是 [10, 5, 3, 22, 11, 2]

当我通过代码程序通过交换开始10和2,然后5和3再2和2.此时,iis 1的值和jis 的值-1.

现在我看到它的方式是有三个条件

1. while(i<=j)哪个回归false,因为i = 1和j = -1

2. if(left < j)哪个回归false,因为left = 0和j = -1

3. 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("\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);
    }
}

非常感谢!

Answer 1

我认为你的问题是你没有完全理解递归。至少从你对问题的描述来看是这样的。

不管怎样，我试图通过跟踪所有变量来简单地遵循你的程序。希望这可以帮助：

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 循环条件是 now 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)，因此它的值也为 true。所以你现在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调用已完成，数组已排序。