插入排序
比如学生按照身高排队,前N-1个同学是有序的,那么第N个同学就一个一个从低到高比较,找到合适的位置插入即可.
代码实现
- 普通插入排序方法
public static void insert(int[] array){
for(int i=1;i<array.length;i++){
//temp:表示待排序的元素
int temp=array[i];
int insertPoint=i-1;
//当前元素比待排序元素temp大
while(insertPoint>=0&&array[insertPoint]>temp){
//当前元素后移一位,留出来的地方给temp插入
array[insertPoint+1]=array[insertPoint];
insertPoint--;
}
array[insertPoint+1]=temp;//找到插入位置,插入元素
}
}
public static void main(String[] args) {
int[] a={1,0,5,2,78,65,78,354,689,687};
insert(a);
}
每次找插入位置的时候,我们都要从头到尾一个一个比较.当数据量大的时候,就需要换一种算法
- 二分插入排序方法
public static void insertTwo(int[] array){
for(int i=1;i<array.length;i++){
int temp=array[i];
if(array[i-1]>temp){
//使用二分法获取相应插入的位置的下标
int insertIndex=binarySearch(0,i-1,temp,array);
for(int j=i;j>insertIndex;j--){
array[j]=array[j-1];
}
array[insertIndex]=temp;
}
}
}
private static int binarySearch(int lowerBound, int upperBound, int target,int[] array) {
int curIndex;
while(lowerBound<upperBound){
curIndex=(lowerBound+upperBound)/2;
if(array[curIndex]>target){
upperBound=curIndex-1;
}else{
lowerBound=curIndex+1;
}
}
return lowerBound;
}