当前位置: 代码迷 >> J2SE >> 一个排序算法的时间复杂度和空间复杂度,该怎么处理
  详细解决方案

一个排序算法的时间复杂度和空间复杂度,该怎么处理

热度:11   发布时间:2016-04-24 13:05:21.0
一个排序算法的时间复杂度和空间复杂度
自己写了一个数组排序的类,请哪位大虾帮我分析一个这个算法的时间复杂度和空间复杂度。
这个类的实现方式利用排序二叉树的中序遍历来实现的。谢谢了
Java code
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下编译运行。

------解决方案--------------------
时间复杂度.nLog2(n)
因为每次查找位置的时候复杂度是 log2(n)
线性增加,所以乘以n

空间复杂度我不知道怎么算了,因为你没有用到辅助空间,但是你又浪费了一个数组,所以如果有的话,应该是o(n)吧
------解决方案--------------------
时间复杂度--->".nLog2(n) "
空间复杂度--->"o(n)"
  相关解决方案