javaFX:错误的合并排序动画结果

Question

我正在使用 javaFX 实现带有一些矩形的合并排序动画。我使用一些动画功能来做到这一点。但是，翻译路线是错误的。我一遍又一遍地检查我的代码，但没有发现问题。问题可能出在合并方法中，但我找不到问题出在哪里。我使用绝对坐标定位节点:javaFX:move shapes with absolute coordinates using translatetransition .谁能帮帮我？？

这些是代码:

public class Main extends Application {
double speed = 400;

int[] helper;

final ArrayList<Integer> CenterX = new ArrayList();
int listindex = 0;
@Override
public void start(Stage primaryStage) throws Exception {

    Pane pane = new Pane();
    ArrayList<StackPane> list = new ArrayList<>();
    Random random = new Random(5);
    for (int i = 0; i < 13; i++) {
        int num = random.nextInt(10);
        Rectangle rectangle = new Rectangle(40, (num * 10) + 50);
        rectangle.setFill(Color.valueOf("#FF7F50"));
        Text text = new Text(String.valueOf(num));
        StackPane stackPane = new StackPane();
        stackPane.setPrefSize(rectangle.getWidth(), rectangle.getHeight());
        stackPane.setId(String.valueOf(num));
        stackPane.getChildren().addAll(rectangle, text);
        StackPane.setAlignment(text,Pos.TOP_CENTER);
        stackPane.setAlignment(Pos.TOP_CENTER);
        stackPane.setTranslateX(60*i);
        list.add(stackPane);
    }


    pane.getChildren().addAll(list);

    BorderPane borderPane = new BorderPane();
    borderPane.setCenter(pane);
    HBox hBox1 = new HBox();
    Button b = new Button("Sort");


    AnchorPane bottomPane = new AnchorPane();
    hBox1.getChildren().add(b);
    bottomPane.getChildren().add(hBox1);     
    borderPane.setBottom(bottomPane);


    b.setOnAction(event -> {
        SequentialTransition sq = new SequentialTransition();
        int[] = arr;
        arr = generateArray(list);
        sq = MergeSort(arr, list,sq);
        b.setDisable(true);
        sq.play();
        sq.setOnFinished(new EventHandler<ActionEvent>() {
            @Override
            public void handle(ActionEvent event) {
                b.setDisable(false);
            }
        });
        b.setDisable(false);

    });

    Scene scene = new Scene(borderPane,800, 800);
    primaryStage.setTitle("Sorting");
    primaryStage.setResizable(false);
    primaryStage.setScene(scene);
    primaryStage.show();

    for (int i = 0; i < 13; i++) {
        int centerx = (int) list.get(i).getLayoutX();
        CenterX.add(i,centerx+60*i);
        System.out.println(centerx+60*i);

    }
}



private int[] generateArray(List<StackPane> list) {
    int arr[] = new int[list.size()];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = Integer.parseInt(list.get(i).getId());
    }
    return arr;
}

private TranslateTransition AddtoOriginal(StackPane sp, double speed,int X){
    TranslateTransition t = new TranslateTransition();
    t.setNode(sp);
    t.setDuration(Duration.millis(speed));
    t.setToX(X);
    t.setToY(300);
    return t;

}

public SequentialTransition MergeSort(int arr[],ArrayList<StackPane> list,SequentialTransition sq) {
    int number = arr.length;
    this.helper = new int[number];
    mergesort(0, number - 1,arr,sq,list);
    return sq;
}

private void mergesort(int low, int high,int arr[],SequentialTransition sq,ArrayList<StackPane> list) {
    // check if low is smaller then high, if not then the array is sorted
    if (low < high) {
            // Get the index of the element which is in the middle
            int middle = low + (high - low) / 2;
            // Sort the left side of the array
            mergesort(low, middle,arr,sq,list);
            // Sort the right side of the array
            mergesort(middle + 1, high,arr,sq,list);
            // Combine them both
            merge(low, middle, high,arr,list,sq);
    }

}


private void merge(int low, int middle, int high,int arr[],ArrayList<StackPane> list,SequentialTransition sq) {
// Copy both parts into the helper array
    for (int i = low; i <= high; i++) {
            helper[i] = arr[i];

    }
    int i = low;
    int j = middle + 1;
    int k = low;
    // Copy the smallest values from either the left or the right side back
    // to the original array

    while (i <= middle && j <= high) {
            if (helper[i] <= helper[j]) {
                    arr[k] = helper[i];
                    sq.getChildren().add(AddtoOriginal(list.get(i),speed,CenterX.get(k)));
                    i++;
            } else {
                    arr[k] = helper[j];
                    sq.getChildren().add(AddtoOriginal(list.get(j),speed,CenterX.get(k)));
                    j++;
            }
            k++;
    }
    // Copy the rest of the left side of the array into the target array
    while (i <= middle) {
            arr[k] = helper[i];
            sq.getChildren().add(AddtoOriginal(list.get(i),speed,CenterX.get(k)));
            k++;
            i++;
    }

    ParallelTransition pl = new ParallelTransition();
    ArrayList<TranslateTransition> Transitionlist = new ArrayList<>(high-low);

    for (int z = low; z <= high; z++) {
        TranslateTransition t = new TranslateTransition();
        t.setNode(list.get(z));
        t.setDuration(Duration.millis(speed));
        t.setByY(-300);
        Transitionlist.add(t);  
}
pl.getChildren().addAll(Transitionlist);
sq.getChildren().add(pl);

}

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

Answer 1

您的代码存在问题以及如何解决这些问题

你的主要问题是，当你做这样的事情时:

arr[k] = helper[j];
sq.getChildren().add(AddtoOriginal(list.get(j),speed,CenterX.get(k)));

您正在做的是使用一些数组(arr 和 helper)来表示要排序的值，然后将这些值移动到数组的位置(在赋值)，但是当您运行 AddToOriginal 例程时，您并没有移动代表视觉显示的列表中的值。所以正在发生的事情是视觉显示与排序数组不同步。

此外，合并排序算法(如您所实现的那样)不是内存中的就地排序，实际上涉及两个数组，arr 数组和helper array，当你分配 arr 值时，帮助程序必须跟踪原始值，这样原始值就不会被覆盖。您需要对视觉表示做同样的事情。对于我根据您的原始代码在下面实现的示例代码，我所做的是添加一个额外的 helperNodes 数组，它以可视形式跟踪 helper 数组的位置引用。

将这两个东西放在一起，每当你交换一个节点时，你都会做一个像这样的额外语句，以使视觉列表与你正在操作的值数组保持一致:

arr[k] = helper[j];
list.set(k, helperNodes[j]);
sq.getChildren().add(move(helperNodes[j], k * SPACING));

另外，请注意交换移动是基于未改变的 helperNodes[j] 元素而不是 list.get(j) 元素，后者可能已经被变异了。上面的代码所做的是通过视觉列表数组的操作和 sq 顺序转换中的动画移动来反射(reflect)值分配的逻辑。

另一个问题是，当要排序的合并段右侧的节点已经有序时，您的合并排序算法不会执行任何操作。但是，您正在执行合并段中所有元素的动画移动，使其返回到它们的原始起始高度。因此，即使数组中的值位置没有改变，您也需要添加一些额外的代码来执行该视觉动画。

如果您觉得这很困难，请不要担心(这并不像 IMO 看起来那么容易 :-)

信用

我猜测(也许是错误的)您的合并排序算法是基于 Vogella Merge Sort Tutorial .如果是这样，很高兴在问题中承认这一点，因为它有助于理解上下文中的灵感来源(如果不是，您可以忽略此注释)。

未排序

排序中

已排序

示例应用

import javafx.animation.*;
import javafx.application.Application;
import javafx.geometry.*;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.layout.*;
import javafx.scene.paint.Color;
import javafx.scene.shape.Rectangle;
import javafx.scene.text.Text;
import javafx.stage.Stage;
import javafx.util.Duration;

import java.util.*;

public class Merge extends Application {
    private static final int N_VALUES = 13;
    private static final int SPACING = 60;
    private static final int SORT_GROUP_MOVE_DELTA = 200;

    private static final Duration SPEED = Duration.millis(400);

    private int[] helper;
    private StackPane[] helperNodes;
    private Random random = new Random(5);

    @Override
    public void start(Stage stage) throws Exception {
        Pane displayPane = new Pane();
        ArrayList<StackPane> list = new ArrayList<>();
        for (int i = 0; i < N_VALUES; i++) {
            StackPane stackPane = createValueNode(i);
            list.add(stackPane);
        }

        displayPane.getChildren().addAll(list);

        Button sortButton = new Button("Sort");
        sortButton.setOnAction(event -> {
            SequentialTransition sq = new SequentialTransition();
            int[] arr = generateArray(list);
            sq = mergeSort(arr, list, sq);
            sortButton.setDisable(true);
            sq.play();
            sq.setOnFinished(event1 -> sortButton.setDisable(false));
            sortButton.setDisable(false);
        });

        BorderPane borderPane = new BorderPane();
        borderPane.setCenter(displayPane);
        borderPane.setBottom(sortButton);
        BorderPane.setAlignment(sortButton, Pos.CENTER);
        BorderPane.setMargin(sortButton, new Insets(10));

        Scene scene = new Scene(borderPane, 800, 400);
        stage.setTitle("Sorting");
        stage.setResizable(false);
        stage.setScene(scene);
        stage.show();
    }

    private StackPane createValueNode(int i) {
        int num = random.nextInt(10);
        Rectangle rectangle = new Rectangle(40, (num * 10) + 50);
        rectangle.setFill(Color.valueOf("#FF7F50"));
        Text text = new Text(String.valueOf(num));
        StackPane stackPane = new StackPane();
        stackPane.setPrefSize(rectangle.getWidth(), rectangle.getHeight());
        stackPane.setId(String.valueOf(num));
        stackPane.getChildren().addAll(rectangle, text);
        StackPane.setAlignment(text, Pos.TOP_CENTER);
        stackPane.setAlignment(Pos.TOP_CENTER);
        stackPane.setTranslateX(SPACING * i);
        return stackPane;
    }


    private int[] generateArray(List<StackPane> list) {
        int arr[] = new int[list.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(list.get(i).getId());
        }
        return arr;
    }

    private TranslateTransition move(StackPane sp, int X) {
        TranslateTransition t = new TranslateTransition();
        t.setNode(sp);
        t.setDuration(SPEED);
        t.setToX(X);
        t.setToY(SORT_GROUP_MOVE_DELTA);
        return t;

    }

    public SequentialTransition mergeSort(int arr[], ArrayList<StackPane> list, SequentialTransition sq) {
        int number = arr.length;
        this.helper = new int[number];
        this.helperNodes = new StackPane[number];
        sortRange(0, number - 1, arr, sq, list);
        return sq;
    }

    private void sortRange(int low, int high, int arr[], SequentialTransition sq, ArrayList<StackPane> list) {
        // check if low is smaller then high, if not then the array is sorted
        if (low < high) {
            // Get the index of the element which is in the middle
            int middle = low + (high - low) / 2;
            // Sort the left side of the array
            sortRange(low, middle, arr, sq, list);
            // Sort the right side of the array
            sortRange(middle + 1, high, arr, sq, list);
            // Combine them both
            merge(low, middle, high, arr, list, sq);
        }
    }


    private void merge(int low, int middle, int high, int arr[], ArrayList<StackPane> list, SequentialTransition sq) {
        // Copy both parts into the helper array
        for (int i = low; i <= high; i++) {
            helper[i] = arr[i];
            helperNodes[i] = list.get(i);
        }

        int i = low;
        int j = middle + 1;
        int k = low;
        // Copy the smallest values from either the left or the right side back
        // to the original array

        while (i <= middle && j <= high) {
            if (helper[i] <= helper[j]) {
                arr[k] = helper[i];
                list.set(k, helperNodes[i]);
                sq.getChildren().add(move(helperNodes[i], k * SPACING));
                i++;
            } else {
                arr[k] = helper[j];
                list.set(k, helperNodes[j]);
                sq.getChildren().add(move(helperNodes[j], k * SPACING));
                j++;
            }
            k++;
        }
        // Copy the rest of the left side of the array into the target array
        while (i <= middle) {
            arr[k] = helper[i];
            list.set(k, helperNodes[i]);
            sq.getChildren().add(move(helperNodes[i], k * SPACING));
            k++;
            i++;
        }

        // Even if we didn't move in the array because it was already ordered, 
        // move on screen for any remaining nodes in the target array.
        while (j <= high) {
            sq.getChildren().add(move(helperNodes[j], k * SPACING));
            k++;
            j++;
        }

        ParallelTransition moveUp = new ParallelTransition();

        for (int z = low; z <= high; z++) {
            TranslateTransition moveNodeUp = new TranslateTransition();
            moveNodeUp.setNode(helperNodes[z]);
            moveNodeUp.setDuration(SPEED);
            moveNodeUp.setByY(-SORT_GROUP_MOVE_DELTA);
            moveUp.getChildren().add(moveNodeUp);
        }

        sq.getChildren().add(moveUp);
    }

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

可能的替代实现

您可以做的一件事是创建一个 SortableNode 类来替换您定义的用于保存值的 StackPane。可排序节点可以将节点的值保存在字段中而不是 ID 中。可排序节点还可以实现 Comparable .然后您的合并排序算法可以更新为将可比较对象列表而不是整数数组作为输入。这样你就不需要为排序中的值和视觉表示跟踪单独的数组算法(并使它们保持同步)。这可能会稍微简化实现。但我不会在这里添加额外的示例来实现这种替代方法(因为上面的当前示例似乎工作得很好 ;-)