插入式排序运行效率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();
}
}
