作者：敲代码の流川枫
博客主页：流川枫的博客
专栏：和我一起学java
语录：Stay hungry stay foolish
工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
文章目录
算法思想
插入排序的主要思想就是，对于未排序的数据，在已排序的序列从后向前扫描，找到相应的位置并插入
既然插入到序列中了，就要给它腾出空间来，我们需要将插入位置之后的已排序元素像右移动一位
插入排序所需要的时间取决于数据的原始顺序，当对部分有序的数据使用插入排序十分高效
算法图解
int[] array = {4,5,2,6,8,7};
以数组array为例分析
for 循环开始，直到i=1,即preIndex=1
45是有序的，preIndex指向5，currentValue指向2，2小于5并且小于4，将两个元素分别后移一位，并且preIndex自减两次为-1，此时找到插入的位置为preIndex+1，即0位置插入2
循环继续，preIndex指向8，currentValue指向7，7小于8，将8后移一位，并且preIndex自减一次为3，找到插入的位置为preIndex+1，即4位置插入7
至此排序完成
代码实现
代码：
import java.util.Arrays;
public class InsertionSort {
public int[] sortArray(int[] nums){
if(nums.length==0){
return nums;
}
int currentValue;//存放当前值，当前值前的数据已经有序
for (int i = 0; i < nums.length-1; i++) {
int preIndex = i;//已被排序的数据的索引
currentValue = nums[preIndex + 1];
//在已排序的数据中倒序寻找比当前数据小的数据，将其后移一位
while(preIndex>=0 && currentValue < nums[preIndex]){
nums[preIndex+1] = nums[preIndex];
preIndex--;
}
//程序走到这里，已经找到合适的插入位置，将当前数据插入
nums[preIndex+1] = currentValue;
System.out.println("本轮插入后的数组");
System.out.println(Arrays.toString(nums));
}
return nums;
}
public static void main(String[] args) {
int nums[] = {3,4,5,2,1,6,10,8};
InsertionSort insertionSort = new InsertionSort();
insertionSort.sortArray(nums);
System.out.println("排序结束");
System.out.println(Arrays.toString(nums));
}
}
运行结果：
算法特点
特点：稳定，相对顺序不会变，在序列基本有序的情况下，排序时间短；最差的情况应该是将序列倒序变成顺序
适用场景：数据基本有序，小数组，要求稳定
时间复杂度：最坏情况下为O(N2)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序
空间复杂度：O(1)
” 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！
原文链接: https://blog.csdn.net/chenchenchencl/article/details/126580227