java数组如何插入元素并快捷排序？

本教程操作环境：windows7系统、java10版，DELL G3电脑。

1、从数组的第二个元素进行操作，如果发现其前面的元素比他大，就将其前面的元素往后挪，直到cur指向的元素大于或者等于他前一个元素，此时cur指向的位置就是待插入元素应该插入的位置。

staticint[]insertSort2(int[]array){

intlen=array.length;

for(intbegin=1;begin<len;begin++){

intcur=begin;

inttmp=array[cur];

while(cur>0&&array[cur]<array[cur-1]){

array[cur]=array[cur-1];

cur--;

}

array[cur]=tmp;

}

returnarray;

}

2、通过二分查找减少了比较次数，即cmp函数的调用，还减少了swap函数的调用。更快的找到了当前元素应该插入的位置，然后再进行挪动，提高了效率。

staticint[]insertSort3(int[]array){

intlen=array.length;



for(intbegin=1;begin<len;begin++){

intv=array[begin];

intinsertIndex=search(array,begin);

//将[insertIndex,begin)范围内的元素往右边挪动一个单位

for(inti=begin;i>insertIndex;i--){

array[i]=array[i-1];

}

array[insertIndex]=v;

}

returnarray;

}

staticintsearch(int[]array,intindex){

intbegin=0;

intend=index;

while(begin<end){

intmid=(begin+end)>>1;

if(array[index]<array[mid]){

end=mid;

}else{

begin=mid+1;

}

}

returnbegin;

}

需要注意的是：使用了二分搜索后，只是减少了比较次数，但插入排序的平均时间复杂度依然是O(n^2)。