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

原文 标签 java algorithm sorting javafx mergesort

我正在使用javafx实现一个带有一些矩形的合并排序动画。我用一些动画的功能来做。然而,翻译路线是错误的。我一遍又一遍地检查代码,没有发现问题问题可能出在merge方法中,但我找不到问题所在。我使用绝对坐标来定位节点: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);
}
}

最佳答案

代码问题及解决方法
你的主要问题是当你做这样的事情时:

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

您要做的是使用一些数组(arrhelper)来表示要排序的值,并在数组中的位置(在赋值中)内移动值,但是当您运行AddToOriginal例程时,您不会同时移动表示可视显示的列表中的值。所以现在的情况是,视觉显示正在变得与排序数组不同步。
此外,合并排序算法(如您所实现的那样)不是内存中的就地排序,实际上涉及两个数组,即arr数组和helper数组,在您分配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顺序转换中的动画移动来镜像值分配的逻辑。
另一个问题是,当要排序的合并段右侧的节点已经排序好时,您所拥有的合并排序算法不会执行任何操作。但是,您将对合并段中的所有元素执行动画移动,使其返回到其原始起始高度。因此,即使数组中的值位置没有改变,也需要添加一些额外的代码来进行可视化动画。
如果你觉得这很难,别担心(这不像我想象的那么容易:-)
信用卡
我猜测(也许是错误的)您的合并排序算法是基于Vogella Merge Sort Tutorial的如果是这样,在问题中承认这一点是很好的,因为它有助于理解上下文中的灵感来源(如果不是,你可以忽略这个注释)。
未分类的
unsorted
正在排序
in progress
已排序
sorted
样例应用程序
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。然后可以更新合并排序算法,将可比较对象的列表作为输入,而不是一个int数组。这样就不需要跟踪排序中的值和可视表示的单独数组
算法(并保持它们同步)这可能会稍微简化实现但我不会在这里添加额外的示例来实现这种替代方法(因为上面的当前示例似乎工作得很好;-)

关于java - javaFX:错误合并排序动画结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43009519/

相关文章:

java - 混合两个数组

java - Java Servlet:以相同的响应写入输出html文本和jpg

java - Primefaces : Select Check Box menu : NullPointerException

c# - 排序混合数字和字符串

c++ - 使用<algorithm>排序对自定义链接列表进行排序

c++ - 模型/ View Qt 文档中关于排序的描述可能是错误的?

java - 试图通过使用复选框将jlabel完全删除/添加到jframe

javascript - 通过递归函数问题无序列表“合并”

java - 如何检查表示路径的字符串是否完全由Java中的3个子目录组成?

algorithm - 对于不同的质量因子和 block 大小,如何针对比特率绘制PSNR行为?