首页 > 代码库 > 算法复杂度，及三种主要排序算法的研究

算法复杂度，及三种主要排序算法的研究

2024-07-07 03:13:28   222人阅读

一、时间复杂度

　　1、时间频度  T(n),n为问题的规模

　　　　即--算法中语句的执行次数。又叫语句频度。

　　2、时间复杂度

　　　　记作 O( f(n) )，这里的f（n）是一个T（n）的同数量级函数。

　　　　 如O(1)表示算法的语句执行次数为一个常数，不随规模n的增长而增长；

　　　　又如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，

　　　　但时间复杂度相同，都为O(n^2)。

　　　　

　　3、算法的性能

　　　　主要用算法的 时间复杂度 的数量级来评价一个算法的时间性能。

二、空间复杂度

　　S（n），包括3方面：

　　1、算法程序的空间

　　2、初始数据所占的空间

　　3、算法执行过程中需要的额外空间

 

三、三种算法---参考了http://blog.chinaunix.net/uid-23860671-id-150518.html

public class MainSort {
    private static int[] data = http://www.mamicode.com/{66,22,55,44,11,33};
    private static int LENGTH = data.length;
    
    public static void main(String args[]){
        System.out.println("hello world");
        sortByChoose();
        System.out.println("result is:");
        printData();
        
    }
    private static void printData() {
        for(int i = 0; i<LENGTH; i++){
            System.out.print("*"+data[i]);
        }
        System.out.print("*");
        System.out.println("");
        
    }
    //选择排序 -- 外层遍历每次找出最小的，放到前面，下次只遍历未排序的后面一段
    private static void sortByChoose(){
        
        for(int unsortSize = LENGTH ; unsortSize>0 ; unsortSize--){
            
            int temp = LENGTH-unsortSize; 
            
            for(int j = LENGTH-unsortSize ; j<LENGTH; j++){ //遍历未排序的找出最小的数的角标
    
                if(data[temp] > data[j]){
                    temp = j;
                }

            }
            System.out.println(""+temp);
            
            int x = data[LENGTH-unsortSize];
            data[LENGTH-unsortSize] = data[temp];
            data[temp] = x;
            
            printData();
        }
    }
    //插入排序
    private static void sortByInsert(){
        
    }
    //冒泡排序
    private static void sortByPop(){
        
    }
}

 

 


联系
我们