1. 图示过程
插入排序图示
2. 动图展示
3. 文字叙述过程
- 第1趟插入：将第2个元素插入前面的有序子序列，此时前面只有一个元素，当然是有序的
- 第2趟比较：将第3个元素插入前面的有序子序列，前面的2个元素是有序的
- ......
- 第n-1趟比较：将第n个元素插入前面的有序子序列，前面n-1个元素是有序的
4. Java代码实现
public static void insertionSort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
for(int i = 1; i < nums.length; i++) {
for(int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--) {
ArrayUtils.swap(nums, j, j + 1);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
5. 复杂度
- 时间复杂度：O(n²)
- 空间复杂度：O(1)，只需要一个额外空间用于交换
- 稳定性：插入排序是稳定的排序算法，满足条件
nums[j] > nums[j + 1]才发生交换，这个条件可以保证值相等的元素的相对位置不变。
6. 优化
上面的算法的缺点：在第i-1趟插入时，需要把第i个元素插入到前面的i-1个元素中，该算法总是从i-1个元素开始逐个比较之前的每个元素，直到找到第i个元素的插入位置，这显然没有利用前面0~i-1个元素已经有序的特点
优化：在0~i-1个有序元素给第i个元素寻找插入的位置时，使用二分查找法可以有效提高查找插入位置的时间效率，经过优化的插入排序称为折半插入排序，折半插入排序的时间复杂度为O(n*logn)
/**
* 折半插入排序
*/
public static void binaryInsertionSort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
for(int i = 1; i < nums.length; i++) {
int temp = nums[i];
// 通过二分查找找到插入的位置
int insertIndex = findInsertIndex(nums, 0, i - 1, nums[i]);
// 插入位置之后的元素依次向后移动
for(int j = i; j > insertIndex; j--) {
nums[j] = nums[j - 1];
}
// 更新插入位置的值
nums[insertIndex] = temp;
}
}
/**
* 在有序数组 nums 的[L, R]部分上，找到 value 的插入位置
*/
public static int findInsertIndex(int[] nums, int L, int R, int value) {
while(L <= R) {
int mid = L + ((R - L) / 2);
if(value > nums[mid]) {
L = mid + 1;
} else {
R = mid - 1;
}
}
return L;
}
