public class Insert_Sort {
public int[] Sort(int data[]){
for(int i=1;i<data.length;i++){
int key=data[i];
int j=i-1;
while(j>=0&& data[j]>key){
data[j+1]=data[j];
j--;
}
data[j+1]=key;
}
return data;
}
}
时间复杂度：最佳情况下：O(n),最坏情况下：O(n^2) 参考算法导论
影响因素：存储的数据结构
设想优化1：运用折半思想：
public int[] Sort(int data[]){
for(int i=1;i<data.length;i++){
int key=data[i];
int j=i-1;
int half=i/2;
if(data[half]<key){
while(j>=half&&data[j]>key){
data[j+1]=data[j];
j--;
}
}else if(data[half]>key){
while(j>=0&&data[j]>key){
data[j+1]=data[j];
j--;
}
}
data[j+1]=key;
}
return data;
}
结果优化失败，原因：需要后移的次数与比较次数无关，数组的数据结构决定了其插入特性。
设想优化2：采用双向链表插入。。。。。。
