直接插入排序算法
@Test
public void test(){
int [] arr = {1,5,3,9,70,55,4};
int i , j;
for (i = 2; i < arr.length; i++){
if (arr[i] < arr[i - 1]){
//复制为哨兵
arr[0] = arr[i];
for (j = i - 1; arr[0] < arr[j]; j--){
//元素后移
arr[j + 1] = arr[j];
}
//插入正确位置
arr[j + 1] = arr[0];
}
}
for (int i1 : arr) {
System.out.println(i1);
}
}
二分直接插入排序 算法
@Test
public void test1(){
int [] arr = {1,5,3,9,70,55,4};
int i , j , low , high , mid;
for (i = 2; i < arr.length;i++){
arr[0] = arr[i];
low = 1;
high = i - 1;
while (low <= high){
mid = (low + high) / 2;
if (arr[0] > arr[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
//循环结束,插入位置为high + 1
for (j = i - 1;j >= high + 1;j--){
arr[j + 1] = arr[j];
}
arr[high + 1] = arr[0];
}
for (int i1 : arr) {
System.out.println(i1);
}
}