代码之家 › 专栏 › 技术社区 › Michael Kiroff

Quicksort 3-way分区代码没有按要求执行

partitioning quicksort algorithm java

Michael Kiroff · 技术社区 · 7 年前

我需要制作一个利用三向分区的快速排序方法。我使用的算法可以在这里找到 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(结束时)lt=9 gt=8(结束时)现在,它应该交换i和lt,并增加i。然而,它没有,我不知道为什么。我的while循环中的条件是while(i<=gt),因此它应该在那一点上继续迭代,因为i和gt处于相同的索引(请参阅代码),但它不是。如果这里有人能帮我修复这个错误,我将非常感谢,我真的要开始拔头发了。

2 回复 | 直到 7 年前

vailodf 7 年前

尝试使用 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++;
    }

Stefan 7 年前

这不是错误修复。只有一些有助于识别问题:

添加更多调试,如下所示:

    System.out.println("Part 1: " + low + " to " + (lt-1));
    System.out.println("Part 2: " + (gt+1) + " to " + high);
    quicksort(array, low, lt -1);
    quicksort(array, gt + 1, high);

Part 1: 0 to 1
Part 2: 4 to 3

这意味着前两项-8,7-将在下一轮排序。但在那之后,自4>3,所以9,8将保持错误的顺序。很明显,如果(在本例中)第2部分是“2到3”,那么一切都没问题。

可悲的是,如何解决这个问题还不太清楚。在这种情况下,以下方法可行,但我怀疑Quicksort不应该这样,在其他情况下可能也不可行:

    quicksort(array, low, lt -1);
    quicksort(array, lt, high);