排序算法中,快速排序是最快的,比较适合用链表来处理,但是链表的查找是比较慢的(双向链表的话可以加快查找速度)。
数组排序会比较慢,不是算法的问题,而是数组的调整因为需要位移,但是数组一旦排号顺序后,查找是很快的——折半查找。
二叉数较为平局,排序可以采用堆排序,查找可以建二叉排序树来找(用B+或B-树的话可以更快)。
个人看法,不一定对,欢迎拍砖,具体代码知道算法了就自己上网找吧。
做了很多年的程序员,觉得什么树的设计并不是非常实用。二叉树有顺序存储,当一个insert大量同时顺序自增插入的时候,树就会失去平衡。树的一方为了不让塌陷,会增大树的高度。性能会非常不好。以上是题外话。分析需求在写代码。import java.util.List
import java.util.LinkedList
public class Bintrees {
private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9}
private static List<Node>nodeList = null
private static class Node {
Node leftChild
Node rightChild
int data
Node(int newData) {
leftChild = null
rightChild = null
data = newData
}
}
// 创建二叉树
public void createBintree() {
nodeList = new LinkedList<Node>()
// 将数组的值转换为node
for (int nodeIndex = 0nodeIndex <array.lengthnodeIndex++) {
nodeList.add(new Node(array[nodeIndex]))
}
// 对除最后一个父节点按照父节点和孩子节点的数字关系建立二叉树
for (int parentIndex = 0parentIndex <array.length / 2 - 1parentIndex++) {
nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1)
nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2)
}
// 最后一个父节点
int lastParentIndex = array.length / 2 - 1
// 左孩子
nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1)
// 如果为奇数,建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2)
}
}
// 前序遍历
public static void preOrderTraverse(Node node) {
if (node == null) {
return
}
System.out.print(node.data + " ")
preOrderTraverse(node.leftChild)
preOrderTraverse(node.rightChild)
}
// 中序遍历
public static void inOrderTraverse(Node node) {
if (node == null) {
return
}
inOrderTraverse(node.leftChild)
System.out.print(node.data + " ")
inOrderTraverse(node.rightChild)
}
// 后序遍历
public static void postOrderTraverse(Node node) {
if (node == null) {
return
}
postOrderTraverse(node.leftChild)
postOrderTraverse(node.rightChild)
System.out.print(node.data + " ")
}
public static void main(String[] args) {
Bintrees binTree = new Bintrees()
binTree.createBintree()
Node root = nodeList.get(0)
System.out.println("前序遍历:")
preOrderTraverse(root)
System.out.println()
System.out.println("中序遍历:")
inOrderTraverse(root)
System.out.println()
System.out.println("后序遍历:")
postOrderTraverse(root)
}
}