Java 实现插入式简单排序

插入式排序运行效率N*(N-1)/4 对于随机数字,这个算法比冒泡快1倍,比选择排序稍微快一点.

如果是基本有序的队列则优势最为明显需要O(N)

 

代码一样是从冒泡排序继承下来的.

 

/**
 *
 * @author leon.lee
 */
public class InsertSort extends BubbleSort {
    public InsertSort(int lengthArray){
        super(lengthArray);
    }
    @Override
    public void sort(){
        int temp = 0;
        for(int i=1;i<arrayData.length;i++){
            temp = arrayData[i];            
            for(int j=i-1;j>=0;j--){
                if(temp<arrayData[j]){
                    arrayData[j+1]=arrayData[j];
                    if(j==0){
                        arrayData[0]=temp;
                    }
                }else{
                    arrayData[j+1]=temp;
                    break;
                }                                
            }            
        }
    }
    public static void main(String[] args) {
        InsertSort bs ;
        try{
            bs = new InsertSort(100);
        }catch(ExceptionInInitializerError e){
            System.out.println(e.getMessage());
            return;
        }
        bs.printArrayList();
        bs.sort();
        bs.printArrayList();
    }
}