java - 快速排序算法的动画

Question

我正在尝试使用 JavaFX 库对快速排序算法的分区部分进行动画处理。我把程序的所有图形部分都写下来了，但我的步骤方法遇到了问题。我的步骤方法中有一个逻辑错误，我似乎无法弄清楚它是什么。每次单击步骤按钮时，步骤方法应该执行一步。

private void quickSort(int lowerIndex, int higherIndex) {

    int i = lowerIndex;
    int j = higherIndex;
    // calculate pivot number, I am taking pivot as middle index number
    int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
    // Divide into two arrays
    while (i <= j) {
        /**
         * In each iteration, we will identify a number from left side which
         * is greater then the pivot value, and also we will identify a number
         * from right side which is less then the pivot value. Once the search
         * is done, then we exchange both numbers.
         */
        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            exchangeNumbers(i, j);
            //move index to next position on both sides
            i++;
            j--;
        }
    }
    // call quickSort() method recursively
    if (lowerIndex < j)
        quickSort(lowerIndex, j);
    if (i < higherIndex)
        quickSort(i, higherIndex);
}

上面的代码是快速排序算法的源代码，step方法应该只执行快速排序算法的一步。我尝试在步骤方法中实现相同的逻辑，但我的逻辑是错误的。该程序的正确输出位于此链接 http://www.cs.armstrong.edu/liang/animation/web/QuickSortPartition.html以供引用。

下面是我正在使用的代码

 import java.util.Arrays;
 import javafx.application.Application;
 import javafx.geometry.Pos;
 import javafx.scene.Scene;
 import javafx.scene.control.Button;
 import javafx.scene.layout.BorderPane;
 import javafx.scene.layout.HBox;
 import javafx.scene.layout.Pane;
 import javafx.scene.paint.Color;
 import javafx.scene.shape.Line;
 import javafx.scene.shape.Rectangle;
 import javafx.scene.text.Text;
 import javafx.stage.Stage;

 public class AnimateQuickSort extends Application {
    public final static int ARRAY_SIZE = 20;
    private int[] array = new int[ARRAY_SIZE];
    private int leftP = 1;
    private int rightP = array.length - 1;
    private int pivot = 0;

public void start(Stage primaryStage) {
    AnimationPane pane = new AnimationPane();

    Button btStep = new Button("Step");
    Button btReset = new Button("Reset");

    HBox hBox = new HBox(5);
    hBox.getChildren().addAll(btStep, btReset);
    hBox.setAlignment(Pos.CENTER);

    BorderPane borderPane = new BorderPane();
    borderPane.setCenter(pane);
    borderPane.setBottom(hBox);

    // Create a scene and place it in the stage
    Scene scene = new Scene(borderPane, 700, 225);
    primaryStage.setTitle("QuickSort");
    primaryStage.setScene(scene);
    primaryStage.show();

    initializeArray();

    pane.repaint();

    btStep.setOnAction(e -> {
        if (step()) {
            pane.repaint();
        } else {
            pane.repaint();
        }
    });

    btReset.setOnAction(e -> {
        reset();
        pane.repaint();
    });
}

public static void main(String[] args) {
    launch(args);
}

public void initializeArray() {

    for (int i = 0; i < array.length; i++) {
        array[i] = (int) (Math.random() * 999 + 1);
    }

    // Arrays.sort(array);

}

public void reset() {
    leftP = 1;
    rightP = array.length - 1;
    pivot = 0;
    initializeArray();
}

public boolean step() {
    // quicksort(array);
    int begin = 0;
    int pivotVal = array[0];
    int array1;

    if (leftP <= rightP && array[leftP] <= pivotVal) {
        leftP++;
        array1 = array[leftP];
        array[leftP] = array[rightP];
        array[rightP] = array1;
    }

    if (rightP >= leftP && array[rightP] > pivotVal) {
        rightP--;
    }
    if (rightP > leftP) {
        if (rightP != begin) {
            array1 = array[rightP];
            array[rightP] = array[begin];
            array[begin] = array1;
        }
    }
    // Return the index of the pivot element.
    return true;
}

class AnimationPane extends Pane {
    private int startingX = 20;
    private int startingY = 20;
    private int boxWidth = 30;
    private int boxHeight = 20;

    protected void repaint() {
        this.getChildren().clear();

        int x = startingX + 10;
        int y = startingY + 40;

        // Display array
        x = startingX + 10;
        getChildren().add(new Text(x - 15, y + 55, "Array "));
        x += 20;
        getChildren().add(new Text(x + pivot * boxWidth, y + 120, "Pivot"));
        drawArrowLine(x + 15 + pivot * boxWidth, y + 100, x + 15 + pivot * boxWidth, y + 40 + boxHeight);

        getChildren().add(new Text(x - 14 + leftP * boxWidth, startingY, "Left Pointer"));
        drawArrowLine(x + 15 + leftP * boxWidth, startingY, x + 15 + leftP * boxWidth, y + 40);

        getChildren().add(new Text(x - 14 + rightP * boxWidth, startingY, "Right Pointer"));
        drawArrowLine(x + 15 + rightP * boxWidth, startingY, x + 15 + rightP * boxWidth, y + 40);

        for (int k = 0; k < array.length; k++) {
            Rectangle rectangle = new Rectangle(x, y + 40, boxWidth, boxHeight);
            rectangle.setFill(Color.WHITE);
            rectangle.setStroke(Color.BLACK);
            getChildren().add(rectangle);
            if (array[k] != 0) {
                getChildren().add(new Text(x + 5, y + 55, array[k] + ""));
            }
            x = x + boxWidth;
        }
    }

    public void drawArrowLine(double x1, double y1, double x2, double y2) {
        getChildren().add(new Line(x1, y1, x2, y2));

        // find slope of this line
        double slope = ((((double) y1) - (double) y2)) / (((double) x1) - (((double) x2)));

        double arctan = Math.atan(slope);

        // This will flip the arrow 45 off of a
        // perpendicular line at pt x2
        double set45 = 1.57 / 2;

        // arrows should always point towards i, not i+1
        if (x1 < x2) {
            // add 90 degrees to arrow lines
            set45 = -1.57 * 1.5;
        }

        // set length of arrows
        int arrlen = 15;

        // draw arrows on line
        getChildren().add(new Line(x2, y2, (x2 + (Math.cos(arctan + set45) * arrlen)),
                ((y2)) + (Math.sin(arctan + set45) * arrlen)));

        getChildren().add(new Line(x2, y2, (x2 + (Math.cos(arctan - set45) * arrlen)),
                ((y2)) + (Math.sin(arctan - set45) * arrlen)));
    }
}
 }

Answer 1

如果没有协程，你就无法单步执行递归函数(Java 中有几个用于协程的库，但其中大多数都调整了 JVM 或字节码，所以不是真正的标准内容)。

你基本上有两个选择:

• 反转职责，如果可以的话:让 QuickSort 调用动画重绘，而不是调用单步 QuickSort 的动画。

• 或者，为了实现执行单步快速排序的函数，您将需要展开递归，这将要求您使用显式的 from- 堆栈来跟踪“深度”对。堆栈以“整个数组”开始；在函数的顶部，您弹出一个状态并对该范围进行排序；当您需要递归时，您将较小的范围插入堆栈；当堆栈为空时，您就完成了。