普通的插入排序比二分插入排序要更快，为什么会这样？
使用10万个随机数测试，普通插入排序752毫秒左右，二分插入排序1928毫秒左右
import java.util.Arrays;
import java.util.Random;
public class Sort {
public static void insertSort(int[] a){
int n = a.length;
int cur;
int j;
for(int i=1;i<n;i++){
cur = a[i];
for(j=i-1;j>=0;j--){
if(a[j] > cur){
a[j+1] = a[j];
}
else{
break;
}
}
a[j+1] = cur;
}
}
public static void binInsertSort(int[] a){
int c;
int insertValue;
int insertIndex;
int n = a.length;
for(int i=1;i<n;i++){
insertValue = a[i];
insertIndex = bSearch1(a,i-1,insertValue);
for(c=i-1;c>=insertIndex+1;c--){
a[c+1] = a[c];
}
a[insertIndex+1] = insertValue;
}
}
public static int bSearch1(int[] a, int n, int key){
int low = 0;
int high = n;
int mid;
while(low<=high){
mid = low + ((high-low)>>1);
if(a[mid] <= key){
if(mid==n || a[mid+1]>key){
return mid;
}
low = mid + 1;
}else {
high = mid - 1;
}
}
return -1;
}
public static int bSearch2(int[] a, int n, int key){
int low = 0;
int high = n;
int mid;
while(low<=high){
mid = low + ((high-low)>>1);
if(a[mid] == key){
return mid;
}else if(a[mid] > key){
high = mid - 1;
}else {
low = mid + 1;
}
}
return low - 1;
}
public static void main(String[] args) {
int n = 100000;
int[] a1 = new int[n];
int[] a2 = new int[n];
for(int i=0;i<n;i++){
int t = new Random().nextInt(n);
a1[i] = t;
a2[i] = t;
}
long l = System.currentTimeMillis();
insertSort(a1);
System.out.println(System.currentTimeMillis()-l);
l = System.currentTimeMillis();
binInsertSort(a2);
System.out.println(System.currentTimeMillis()-l);
}
}
