JavaFx 排序可视化工具

Question

我正在开发一个JavaFX 中的排序可视化器项目。我已经成功地实现了冒泡排序和插入排序，但是我在实现快速排序时遇到了问题。

下面的代码是我的快速排序实现。当移除视觉面时，逻辑就起作用了。

    private void quickSort(int[] arr, int high) {
        new Thread(() -> {
            enableButton(true);
            quickSortHelper(arr, 0, high);
        }).start();
    }

    private void quickSortHelper(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSortHelper(arr, low, pi - 1);
            quickSortHelper(arr, pi + 1, high);
        }
    }

    private void qSwapHelper(int[] arr, int i, int j) {
        CountDownLatch latch = new CountDownLatch(1);
        Platform.runLater(() -> {
            swapBarsWithAnimation((Rectangle) mainAPane.getChildren().get(i), (Rectangle) mainAPane.getChildren().get(j), latch);
        });

        try {
            latch.await();
        } catch (Exception _) {
        }

        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private int partition(int[] arr, int low, int high) {
        // choose the pivot
        int pivot = arr[high];

        int i = low-1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                qSwapHelper(arr, i, j);
            }
        }
        qSwapHelper(arr, i+1, high);
        return (i+1);
    }

下面是我管理动画的方法。我正在使用 2 个翻译转换，它们与并行转换同时运行。完成后，锚点将在锚点窗格中更新，并且条形图将被删除，然后在其交换位置中读取以逻辑地反映视觉状态。

    private void swapBarsWithAnimation(Rectangle bar1, Rectangle bar2, CountDownLatch latch) {
        double bar1Pos = AnchorPane.getLeftAnchor(bar1);
        double bar2Pos = AnchorPane.getLeftAnchor(bar2);

        TranslateTransition bar1ToBar2Transition = new TranslateTransition(Duration.millis(DURATION_TIME), bar1);
        bar1ToBar2Transition.setByX(bar2Pos - bar1Pos);

        TranslateTransition bar2ToBar1Transition = new TranslateTransition(Duration.millis(DURATION_TIME), bar2);
        bar2ToBar1Transition.setByX(bar1Pos - bar2Pos);

        ParallelTransition pt = new ParallelTransition(bar1ToBar2Transition, bar2ToBar1Transition);

        Double finalBar2Pos = bar2Pos;
        Double finalBar1Pos = bar1Pos;
        pt.setOnFinished(_ -> {
            AnchorPane.setLeftAnchor(bar1, finalBar2Pos);
            AnchorPane.setLeftAnchor(bar2, finalBar1Pos);

            ObservableList<Node> children = mainAPane.getChildren();

            int indexOfBar1 = children.indexOf(bar1);
            int indexOfBar2 = children.indexOf(bar2);

            children.removeAll(bar1, bar2);
            children.add(indexOfBar1, bar2);
            children.add(indexOfBar2, bar1);

            bar1.setTranslateX(0);
            bar2.setTranslateX(0);

            latch.countDown();
        });

        pt.play();
    }

我的理解是，任何视觉效果都需要在 JavaFX 主线程上运行，因此我使用

Platform.RunLater()

来实现这一点。正如之前提到的，我的冒泡排序和插入工作得很好，所以这可能与递归的使用有关？

我正在考虑将转换添加到队列或列表中然后执行它们，这样它们肯定会按顺序运行？

我打算添加更多排序，包括合并排序，我想我也会遇到同样的问题。

非常感谢任何帮助，我有点卡住了。

Answer 1

来自评论：

通过调试，我注意到快速排序中第 1 条和第 2 条的索引通常是相同的

这将导致“重复子错误”。如果索引相同，则对条的两个引用引用同一节点：即

bar1 == bar2

。然后

children.removeAll(bar1, bar2);

只会删除一个（也是唯一的）栏，

children.add(indexOfBar1, bar2);

将重新添加栏，并且

children.add(indexOfBar2, bar1);

将尝试第二次添加它，并抛出异常。

另请注意，如果

i > j

，这将以不同的方式失败，因为

children.add(indexOfBar1, bar2);

会将

bar2

添加到列表中的错误位置。

感觉好像

i >= j

的情况永远不会出现，但快速排序是一个相当复杂的算法，并且至少在分区

*

的某些实现中，^{i == j}可能是有效的场景。

交换条形的更可靠方法是创建一个临时列表，在临时列表中交换它们，然后将临时列表复制回子列表：

    pt.setOnFinished(_ -> {
        AnchorPane.setLeftAnchor(bar1, finalBar2Pos);
        AnchorPane.setLeftAnchor(bar2, finalBar1Pos);

        ObservableList<Node> children = mainAPane.getChildren();

        int indexOfBar1 = children.indexOf(bar1);
        int indexOfBar2 = children.indexOf(bar2);

        //children.removeAll(bar1, bar2);
        //children.add(indexOfBar1, bar2);
        //children.add(indexOfBar2, bar1);

        List<Node> bars = new ArrayList<>(children);
        Node temp = bars.get(indexOfBar1);
        bars.set(indexOfBar1, bars.get(indexOfBar2));
        bars.set(indexOfBar2, temp);
        children.setAll(bars);

        bar1.setTranslateX(0);
        bar2.setTranslateX(0);

        latch.countDown();
    });

^* 如果可以允许我讲一个轶事的话，我父亲的第一份工作是编写一个 Algol 编译器，他的老板是 Tony Hoare。这大约是霍尔刚刚发明快速排序的时间。我父亲说，他和他的同事花了很多时间试图理解快速排序的工作原理和原因，但他们中没有人能够真正解释为什么它在大多数情况下如此有效。他们推测托尼·霍尔也从未真正理解过他自己的算法（尽管我怀疑情况确实如此）。