插入排序的基本思想: 主要分为两个区间, 无序区间和有序区间, 每次选择无序区间的第一个元素, 在有序区间内选择合适的位置进行插入操作.
插入过程如下图所示:
代码:
public class InsertSort {
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i-1;
for (; j >= 0; j--) {
if (array[j] > tmp) {
array[j+1] = array[j];
} else {
break;
}
}
array[j+1] = tmp;
}
}
public static void main(String[] args) {
int[] arr = {3,2,5,7,1,6,8,9,4};
System.out.println(Arrays.toString(arr));
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
}
运行结果:
性能分析:
折半插入的详细过程如下:
代码:
public class InsertSort {
public static void bsInsertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int left = 0;
int right = i;
while (left < right) {
int aver = (left + right) / 2;
if (tmp >= array[aver]) {
left = aver + 1;
} else {
right = aver;
}
}
for (int j = i; j > left; j--) {
array[j] = array[j-1];
}
array[left] = tmp;
}
}
public static void main(String[] args) {
int[] arr = {3,2,5,7,1,6,8,9,4};
System.out.println(Arrays.toString(arr));
bsInsertSort(arr);
System.out.println(Arrays.toString(arr));
}
}
运行结果:
性能分析:
