JavaFX排序可视化工具快速排序实现问题求助

问题背景 #

开发JavaFX排序可视化项目，已实现冒泡排序、插入排序的可视化逻辑，但快速排序加入动画后出现异常——移除可视化部分时排序逻辑正常运行，推测问题出在递归调用与动画的并发执行上。已知可视化操作需在JavaFX主线程执行，已使用Platform.runLater，但递归的分治特性导致多分支同时触发动画，引发UI混乱。后续计划实现归并排序，预计会遇到同类问题。

现有代码分析 #

快速排序实现代码 #

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);
}

动画管理代码 #

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();
}

核心问题 #

1. 递归并发导致动画混乱：快速排序的分治递归会同时触发左右子分区的排序逻辑，多个后台线程分支同时调用qSwapHelper，导致多个动画任务同时提交到UI线程，打乱了排序的可视化顺序。
2. 数组与UI索引不同步：后台线程中数组的交换操作在latch.await()后执行，但UI中mainAPane的子节点顺序调整是在动画完成后，递归过程中数组索引对应的UI元素可能已经变化，导致后续getChildren().get(i)获取的元素错误。

解决方案：异步链式串行化动画 #

用CompletableFuture替代CountDownLatch，将所有排序步骤（交换、分区、递归）串成异步执行链，确保每个动画完成后再执行下一个排序逻辑，彻底避免并发冲突。

修改后的代码示例 #

1. 交换方法改为返回异步任务

private CompletableFuture<Void> qSwapHelper(int[] arr, int i, int j) {
    CompletableFuture<Void> future = new CompletableFuture<>();
    Platform.runLater(() -> {
        swapBarsWithAnimation((Rectangle) mainAPane.getChildren().get(i), (Rectangle) mainAPane.getChildren().get(j), future);
    });
    // 动画完成后执行数组交换
    return future.thenRun(() -> {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    });
}

2. 动画方法适配CompletableFuture

private void swapBarsWithAnimation(Rectangle bar1, Rectangle bar2, CompletableFuture<Void> future) {
    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);

        // 标记动画完成
        future.complete(null);
    });

    pt.play();
}

3. 分区方法改为异步链式执行

private CompletableFuture<Integer> partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    // 初始化空的异步任务链
    CompletableFuture<Void> sequence = CompletableFuture.completedFuture(null);

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // 链式添加交换任务，确保顺序执行
            sequence = sequence.thenCompose(v -> qSwapHelper(arr, i, j));
        }
    }

    // 完成最后一次交换后返回分区索引
    return sequence.thenCompose(v -> qSwapHelper(arr, i + 1, high))
                   .thenApply(v -> i + 1);
}

4. 递归方法改为异步链式调用

private CompletableFuture<Void> quickSortHelper(int[] arr, int low, int high) {
    if (low >= high) {
        return CompletableFuture.completedFuture(null);
    }

    // 分区完成后，链式执行左右子分区的排序
    return partition(arr, low, high)
           .thenCompose(pi -> quickSortHelper(arr, low, pi - 1)
                               .thenCompose(v -> quickSortHelper(arr, pi + 1, high)));
}

5. 启动排序方法调整

private void quickSort(int[] arr, int high) {
    new Thread(() -> {
        enableButton(true);
        quickSortHelper(arr, 0, high)
           .whenComplete((v, e) -> {
               // 排序完成后在主线程恢复按钮状态
               Platform.runLater(() -> enableButton(false));
           });
    }).start();
}

后续扩展（归并排序适配） #

归并排序同样是分治递归逻辑，可复用这套异步链式方案：

1. 将归并过程中的元素移动操作封装为返回CompletableFuture的方法；
2. 归并的分治步骤通过thenCompose链式执行，确保每个可视化步骤完成后再进行下一步；
3. 保持UI操作在主线程执行，动画串行化。

内容的提问来源于stack exchange，提问作者Liam