java基于BST排序
时间: 2024-03-24 11:38:32 浏览: 21
基于二叉搜索树(Binary Search Tree,简称 BST)的排序算法,也称为二叉排序树排序或者BST排序,是一种利用二叉搜索树来进行排序的算法。BST排序算法的基本思路是将待排序的所有元素插入到一棵二叉搜索树中,然后按照中序遍历的顺序访问所有节点,就可以得到有序的序列。
下面是 Java 中基于 BST 排序的实现代码:
```java
public class BSTSort {
private class Node {
private final int value;
private Node left;
private Node right;
public Node(int value) {
this.value = value;
}
public void insert(int value) {
if (value < this.value) {
if (left == null) {
left = new Node(value);
} else {
left.insert(value);
}
} else {
if (right == null) {
right = new Node(value);
} else {
right.insert(value);
}
}
}
public List<Integer> inorderTraversal() {
List<Integer> result = new ArrayList<>();
if (left != null) {
result.addAll(left.inorderTraversal());
}
result.add(value);
if (right != null) {
result.addAll(right.inorderTraversal());
}
return result;
}
}
public void sort(int[] array) {
if (array == null || array.length == 0) {
return;
}
Node root = new Node(array[0]);
for (int i = 1; i < array.length; i++) {
root.insert(array[i]);
}
List<Integer> sortedList = root.inorderTraversal();
for (int i = 0; i < sortedList.size(); i++) {
array[i] = sortedList.get(i);
}
}
}
```
在上面的代码中,我们定义了一个 BSTSort 类,其中定义了一个内部类 Node 用来表示二叉搜索树的节点。在 insert() 方法中,我们首先比较要插入的元素和当前节点的值的大小关系,如果要插入的元素小于当前节点的值,就递归调用左子树的 insert() 方法;否则递归调用右子树的 insert() 方法。在 inorderTraversal() 方法中,我们采用中序遍历的方式遍历整棵树,将遍历的结果存储在一个 List 中,并返回这个 List。
在 sort() 方法中,我们首先创建了一个节点值为数组第一个元素的二叉搜索树,然后依次将数组中的其他元素插入到这个树中。最后,我们调用根节点的 inorderTraversal() 方法,得到排序后的结果,并将其赋值给原数组。