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

Question

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

为了了解该算法如何对数组中的数字进行排序，我决定在 Eclipse 调试器中逐步完成我的代码步骤 window。

现在有一个步骤，我经历了数百次也无法理解。

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

当我查看代码时，程序首先交换 10 和 2，然后是 5 和 3，然后是 2 和 2。此时 i 的值为 1，j 的值为 -1.

现在我看到的是三个条件

while(i<=j) 其中 returns false，因为 i = 1 和 j = -1
if(left < j) 其中 returns false，因为 left = 0 和 j = -1
if(i < right) 这也是 returns false，因为 i = 1 和 right = 1

但令我惊讶的是，当程序到达 public static void display 之前的最后一个括号时，程序跳回到第 40 行 if(i < right) 但是 right、i、j 和 pivot 的值突然从 5、2、-1 变为和 3 分别。

如果有人能解释为什么值会发生变化，我将非常感激不尽。

我还添加了两张图片，展示了我在 Eclipse 上看到的内容 window 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);
    }
}

非常感谢！

Answer 1

你的第一张图显示调试器在快速排序的两次递归调用中：从main调用快速排序，然后在第38行再次调用快速排序（这是快速排序的原理，它是一种递归策略）。所以你看到你在内部调用的第 40 行，然后当你从那里开始时，你回到之前的快速排序调用（调试器在左上角显示两行而不是三行 window)，你又回到了 pivot 的先前值，等等。数组按原样传递给所有递归调用，因此它是共享的，但整数变量不是。

我认为这里是递归导致难以理解，请检查您的调用堆栈。

Answer 2

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

无论如何，我试图通过跟踪所有变量来简单地遵循您的程序。希望这会有所帮助：

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）所以这个调用结束了你 return 回到原来的位置。那是吗？上面table的第一个条件。变量和参数的状态现在是：

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]。我将跳过这部分，因为它根本不会更改数组。

递归调用完成后，我们return回到原来的位置，现在将检查第二个条件。 i < right (5 < 5) 是 false 这样我们就完成了。

最初的 quicksort 调用已完成，数组已排序。

Answer 3

您使用打印语句和调试器研究排序算法的努力值得称赞！但是您当前的 Quicksort 实现相当难以理解，至少在最初阶段是这样，因为它同时进行了迭代和递归（即您使用循环，同时，您有一个过程 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);                                                      
    }                                                                              
  }

就是这样！不美吗？好吧，是的。您只需：

分区给定数组。在我看来，分区是解决棘手问题的优雅程序。问题很简单：给定一个数字数组，重新排列数组，使得其中有一个数字，其左边的所有数字都小于或等于它，并且所有右边大于或等于它的数字 -- return 数组中此类元素的索引。我强烈建议您尝试自己解决这个问题。维基百科上给出的两个程序（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 procedure 并查看其工作是否令您满意。

就是这样。如果您现在想使用调试器对其进行调试，那么您完全有能力做到这一点。这是 entire implementation.

现在，将这个递归过程转换为迭代过程的问题非常有趣，这个文档：（无耻的插件：我写的）http://bit.ly/recurse-iterate 应该会给你一些线索。将上述快速排序过程实际转换为迭代过程留给 reader :-).

作为练习。

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

Java Quicksort why / where do the values change?

java

eclipse

sorting

algorithm

quicksort