二叉树排序，比选择排序，冒泡排序快很多

*初始化一个长度是100000的随机数字的数组

初始化完毕

接下来分别用3种算法进行排序

选择法排序，一共耗时 15477 毫秒

冒泡法排序，一共耗时 15801 毫秒

二叉树排序，一共耗时 92 毫秒

查看排序结果，是否是不同的数组对象

[[email protected]

[[email protected]

[[email protected]

查看排序结果，内容是否相同

比较 选择法 和 冒泡法 排序结果：

true

比较 选择法 和 二叉树 排序结果：

true*

//二叉树的插入和中序遍历所有的节点

public class Node {

//左子节点

public Node leftNode;

//右子节点

public Node rightNode;

//值

public Object value;

//插入数据

public void add(Object v) {

//如果当前节点没有值，就把数据放在当前节点上

if(nullvalue) {

value = v;

}

//如果当前节点有值，就进行判断，新增的值与当前值的大小关系

else {

//新增的值，比当前值小或者相同

if( (Integer)v - (Integer)value <=0 ) {

if(nullleftNode) {

leftNode = new Node();

}

leftNode.add(v);

}else{

//新增的值，比当前值大

if(null==rightNode) {

rightNode = new Node();

}

rightNode.add(v);

}

}

}

//中序遍历所有的节点

public List values(){

List values = new ArrayList<>();

//左节点的遍历结果

if(null != leftNode) {

values.addAll(leftNode.values());

}

//当前节点

values.add(value);

//有节点的遍历结果

if(null != rightNode) {

values.addAll(rightNode.values());

}

return values;

}

public static void main(String[] args) {

int randoms[] = new int[] { 67, 7, 30, 73, 10, 0, 78, 81, 10, 74 };

Node roots = new Node();

for (int number : randoms) {

roots.add(number);

}

//System.out.println(roots.leftNode.rightNode.value);

System.out.println(roots.values());

}

}

//三种排序的代码比较

public class SortCompare {

public static void main(String[] args) {

//初始化随机数

int total = 100000;

System.out.println(“初始化一个长度是”+total+“的随机数字的数组”);

int[] originalNumbers = new int[total];

for (int i = 0; i < total; i++) {

originalNumbers[i] = (int) (Math.random()*total);

}

System.out.println(“初始化完毕”);

System.out.println(“接下来分别用3种算法进行排序”);

//从初始化了的随机数组复制过来，以保证，每一种排序算法的目标数组，都是一样的

int[] use4sort;

use4sort = Arrays.copyOf(originalNumbers, originalNumbers.length);

int[] sortedNumbersBySelection = performance(new SelectionSort(use4sort),“选择法”);

use4sort = Arrays.copyOf(originalNumbers, originalNumbers.length);
	int[] sortedNumbersByBubbling=performance(new BubblingSort(use4sort),"冒泡法");
    
	use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length);
    int[] sortedNumbersByTree=performance(new TreeSort(use4sort),"二叉树");

    System.out.println("查看排序结果，是否是不同的数组对象");
    System.out.println(sortedNumbersBySelection);
    System.out.println(sortedNumbersByBubbling);
    System.out.println(sortedNumbersByTree);
  
    System.out.println("查看排序结果，内容是否相同");
    System.out.println("比较 选择法 和 冒泡法  排序结果：");
    System.out.println(Arrays.equals(sortedNumbersBySelection, sortedNumbersByBubbling));
    System.out.println("比较 选择法 和 二叉树  排序结果：");
    System.out.println(Arrays.equals(sortedNumbersBySelection, sortedNumbersByTree));
}
interface Sort{
	void sort();
	int[] values();
}
static class SelectionSort implements Sort{
	int numbers[];
	SelectionSort(int[] numbers){
		this.numbers = numbers;
	}
	@Override
	public void sort() {
		for (int i = 0; i < numbers.length; i++) {
			for (int j = i+1; j < numbers.length; j++) {
				if(numbers[j]<numbers[i]){
					int temp = numbers[i];
					numbers[i] = numbers[j];
					numbers[j] = temp;
				}
			}
		}	
	}
	@Override
	public int[] values() {
		return numbers;
	}
}
static class BubblingSort implements Sort{
	int[] numbers;
	BubblingSort(int[] numbers){
		this.numbers = numbers;
	}
	@Override
	public void sort() {
		for (int i = 0; i < numbers.length; i++) {
			for (int j = 0; j < numbers.length-i-1; j++) {
				if(numbers[j]>numbers[j+1]) {
					int temp = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] = temp;
				}
				
			}
		}
	}
	@Override
	public int[] values() {
		return numbers;
	}
}
static class TreeSort implements Sort{
	int numbers[];
	Node n;
	TreeSort(int[] numbers){
		this.numbers = numbers;
		n = new Node();
	}
	@Override
	public void sort() {
		for(int i : numbers ){
			n.add(i);
		}
	}
	@Override
	public int[] values() {
		List<Object> values = n.values();
		int[] sortedNumbers = new int[values.size()];
		for (int i = 0; i < sortedNumbers.length; i++) {
			sortedNumbers[i] = (int)values.get(i);
		}
		return sortedNumbers;
	}
}
private static int[] performance(Sort algorithm, String type) {
	long start = System.currentTimeMillis();
	algorithm.sort();
	int[] values = algorithm.values();
	long end = System.currentTimeMillis();
	System.out.printf("%s排序，一共耗时 %d 毫秒%n",type,end-start);
	return values;
}
           

}