java - Quicksort 3 方式分区代码没有按要求执行

Question

我需要制作一个利用 3 向分区的快速排序方法。我正在使用的算法可以在这里找到 https://algs4.cs.princeton.edu/lectures/23DemoPartitioning.pdf向下滚动到 Dijkstra 3 向分区演示。对于某些数组，例如 5 5 7 3 5 1 6 2 4 8，我的方法有效。但是，当我放置诸如 5 5 7 3 5 1 6 2 4 8 9 8 之类的数组时，我的代码无法正常工作。我得到输出:1 2 3 4 5 5 5 6 7 8 9 8。我知道问题出在哪里，但我不明白为什么我的代码没有处理它。这是我的代码:

import java.util.Scanner;

public class QuickSortDriver {

    public static void main(String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        System.out.print("\n\nEnter array elements: ");
        String s = scan.nextLine();
        String[] token = s.split(" ");
        int[] array = new int[token.length];

        for(int i=0; i < array.length; i++)
            array[i] = Integer.parseInt(token[i]);

        quicksort(array, 0, array.length - 1);

        System.out.print("\nSorted array: ");

        for(int i = 0; i < array.length; i++)
            System.out.printf("%d ", array[i]);

        System.out.print("\n\n");
        scan.close();
    }

    public static void quicksort(int [] array, int low, int high)
    {
        //debugging: shows what the array is
        //before the while loop
        System.out.print("\n");
        for(int j = low; j <= high; j++)
            System.out.printf("%d ", array[j]);

        if(high <= low) 
            return;

        int lt = low;
        int gt = high;
        int i = low;

        while(i <= gt)
        {
            if(array[i] < array[low])
                swap(array, lt++, i++);
            else if(array[i] > array[low])
                swap(array, i, gt--);
            else
                i++;
        }

        //debugging: shows what the array is
        //after the while loop
        System.out.print("\n");
        for(int j = low; j <= high; j++)
            System.out.printf("%d ", array[j]);

        quicksort(array, low, lt -1);
        quicksort(array, gt + 1, high);
    }

    public static void swap(int array[], int i, int j)
    {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

}

出于调试目的，我将打印数组的 for 循环放在排序方法的开头和结尾，通过这样做我发现了问题。这是我的输入输出，其中打印了调试语句:

Enter array elements: 5 5 7 3 5 1 6 2 4 8 9 8

5 5 7 3 5 1 6 2 4 8 9 8 
4 3 2 1 5 5 6 5 8 9 8 7 
4 3 2 1 
3 2 1 4 
3 2 1 
2 1 3 
2 1 
1 2 
1 



6 5 8 9 8 7 
5 6 9 8 7 8 
5 
9 8 7 8 
8 7 9 8 <--right here is the problem
8 7 
7 8 
7 


Sorted array: 1 2 3 4 5 5 5 6 7 8 9 8 

当我的程序到达数组的 9 8 7 8 部分时，它应该这样做:

(请遵循Dijkstra 3路划分算法中的逻辑。)

9 8 7 8

i = 9 lt = 9 gt = 8(at end) increment i

9 8 7 8

i = 8 lt = 9 gt = 8(at end) swap i and lt and increment i

8 9 7 8

i = 7 lt = 9 gt = 8(at end) swap i and lt and increment i

8 7 9 8

i = 8(at end) lt = 9 gt = 8(at end) 现在，它应该交换 i 和 lt 并递增 i。但是，它没有，我不知道为什么。我的 while 循环中的条件是 while(i <= gt)，因此它应该在那个点继续迭代，因为 i 和 gt 位于相同的索引处(请参阅代码)，但事实并非如此。如果这里有人可以帮助我修复这个错误，我将不胜感激，我真的要开始拔头发了。

Answer 1

尝试在 while 循环中使用 lt 而不是 low。它应该看起来像这样:

    while(i <= gt)
    {
        if(array[i] < array[lt])
            swap(array, lt++, i++);
        else if(array[i] > array[lt])
            swap(array, i, gt--);
        else
            i++;
    }