插入排序图示
public static void insertionSort(int[] nums) {
int temp;
for(int i = 1; i < nums.length; i++) {
for(int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--) {
temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
上面的算法的缺点:在第i-1趟插入时,需要把第i个元素插入到前面的i-1个元素中,该算法总是从i-1个元素开始逐个比较之前的每个元素,直到找到第i个元素的插入位置,这显然没有利用前面0~i-1个元素已经有序的特点
优化:在0~i-1个有序元素给第i个元素寻找插入的位置时,使用二分查找法可以有效提高查找插入位置的时间效率,经过优化的插入排序称为折半插入排序
public static void binaryInsertionSort(int[] nums) {
for(int i = 1; i < nums.length; i++) {
int left = 0;
int right = i - 1;
int temp = nums[i];
// 通过二分查找找到插入的位置
while(left <= right) {
int mid = (left + right) / 2;
if(temp > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 插入位置之后的元素依次向后移动
for(int j = i; j > left; j--) {
nums[j] = nums[j - 1];
}
// 更新插入位置的值
nums[left] = temp;
}
}