欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

简单排序:插入排序 博客分类: Sort  

程序员文章站 2024-02-04 16:47:10
...
    public void insertSort(int[] array){
        int temp;
        
        for(int i=1;i<array.length;i++){
            temp = array[i];
            
            for(int k=i-1;k>=0;k--){
                if(array[k] > temp){
                    array[k+1] = array[k];
                    
                    if(k == 0){
                        array[k] = temp;
                    }
                }else{
                    if((k+1) < i){
                        array[k+1] = temp;
                    }
                    break;
                }
            }
        }
    }


效率:
需要进行N(N-1)/2次比较,平均进行N*(N-1)/4次交换,时间复杂度为:O(N^2)