自己写了一个数组排序的类,请哪位大虾帮我分析一个这个算法的时间复杂度和空间复杂度。
这个类的实现方式利用排序二叉树的中序遍历来实现的。谢谢了package csdn;import java.util.Date;
import java.util.Random;public class TreeSort { public static void main(String[] args) {
Integer[] ora = new Integer[20];
Random r = new Random(new Date().getTime());
for (int i = 0; i < 20; i++) {
ora[i] = r.nextInt(1000);
System.out.printf("%d->", ora[i]);
}
System.out.println();
Tree<Integer> root = sortArray(ora);
lastOrder(root);
System.out.println();
} public static <T extends Comparable> void lastOrder(Tree<T> root) {
if (root != null) {
if (root.left != null)
lastOrder(root.left);
System.out.printf("%d->", root.data);
if (root.right != null)
lastOrder(root.right);
}
} public static <T extends Comparable<T>> Tree<T> sortArray(T[] ora) {
Tree<T> result = new Tree<T>();
if (ora.length > 0)
result.data = ora[0];
T data;
Tree<T> temp = result;
for (int i = 1; i < ora.length; i++) {
temp = result;
data = ora[i];
while (temp != null) {
if (data.compareTo(temp.data) <= 0) {
if (temp.left != null) {
temp = temp.left;
continue;
} else {
temp.left = new Tree<T>();
temp.left.data = data;
break;
}
} else {
if (temp.right != null) {
temp = temp.right;
continue;
} else {
temp.right = new Tree<T>();
temp.right.data = data;
break;
}
}
}
}
return result;
}
}
class Tree<T extends Comparable> { public Tree<T> left = null;
public Tree<T> right = null;
public T data;
}代码在jdk1.5下编译运行。
这个类的实现方式利用排序二叉树的中序遍历来实现的。谢谢了package csdn;import java.util.Date;
import java.util.Random;public class TreeSort { public static void main(String[] args) {
Integer[] ora = new Integer[20];
Random r = new Random(new Date().getTime());
for (int i = 0; i < 20; i++) {
ora[i] = r.nextInt(1000);
System.out.printf("%d->", ora[i]);
}
System.out.println();
Tree<Integer> root = sortArray(ora);
lastOrder(root);
System.out.println();
} public static <T extends Comparable> void lastOrder(Tree<T> root) {
if (root != null) {
if (root.left != null)
lastOrder(root.left);
System.out.printf("%d->", root.data);
if (root.right != null)
lastOrder(root.right);
}
} public static <T extends Comparable<T>> Tree<T> sortArray(T[] ora) {
Tree<T> result = new Tree<T>();
if (ora.length > 0)
result.data = ora[0];
T data;
Tree<T> temp = result;
for (int i = 1; i < ora.length; i++) {
temp = result;
data = ora[i];
while (temp != null) {
if (data.compareTo(temp.data) <= 0) {
if (temp.left != null) {
temp = temp.left;
continue;
} else {
temp.left = new Tree<T>();
temp.left.data = data;
break;
}
} else {
if (temp.right != null) {
temp = temp.right;
continue;
} else {
temp.right = new Tree<T>();
temp.right.data = data;
break;
}
}
}
}
return result;
}
}
class Tree<T extends Comparable> { public Tree<T> left = null;
public Tree<T> right = null;
public T data;
}代码在jdk1.5下编译运行。
因为每次查找位置的时候复杂度是 log2(n)
线性增加,所以乘以n空间复杂度我不知道怎么算了,因为你没有用到辅助空间,但是你又浪费了一个数组,所以如果有的话,应该是o(n)吧
空间复杂度--->"o(n)"
空间复杂度是o(n)应该没问题了。