一、简单释义
1、算法概念
对插入第i个记录时，R1、R2、…、Ri-1均已排好顺序。因此，将第i个记录Ri-1、…、R2、R1进行比较，找到合适的位置插入，他简单明了但是速度很慢。
2、算法目的
把无序数组通过彼此之间比较进行移动形成一个有序数组
3、算法思想
将一个记录插入到已经排好序的有序表中，从而一个新的并且记录数增1的有序表。
二、核心思想
旧–已经排序好的有序表；
新–有序表插入一个新的记录，形成一个新的有序表；
三、图形展示
1、第一次排序：首先2和8进行比较，8比2大所以不交换位置。
2、第二次排序：首先1和8进行比较，1比8小所以交换位置，然后1和2进行比较，1比2小交换位置。
3、第三次排序：首先4和8进行比较，4比8小所以交换位置，然后4和2进行比较，4比2大不交换位置，最后4和1进行比较，4比1大不交换位置。
4、第四次排序：首先9和8进行比较，9比8大所以不交换位置，后面以此类推。
四、代码实现
/** * @BelongsProject: demo * @BelongsPackage: com.wzl.Algorithm.Partition * @Author: Wuzilong * @Description: 直接插入排序 * @CreateTime: 2023-04-26 09:27 * @Version: 1.0 */ public class InsertionSort { public static void insertionSort(int[] num){ for (int i =1; i<num.length;i++){ if (num[i]<num[i-1]){ int temp=num[i]; for (int j=i; j>=0;j--){ if (j>0&&num[j-1]>temp){ num[j]=num[j-1]; }else{ num[j]=temp; break; } } } System.out.println(Arrays.toString(num)); } } public static void main(String[] args) { int[] num={2,8,1,4,9,5,7}; insertionSort(num); }
运行结果
五、算法描述
1、问题描述
每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止
2、算法过程
整个算法过程分为以下几步：
1）每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
2）第一趟比较前两个数，然后把第二个数按大小插入到有序表中。
3）第二趟把第三个数据与前两个数从后向前比较，把第三个数按大小插入到有序表中。
4）依次进行下去，进行了(n-1)趟比较以后就完成了整个排序过程。
3、算法总结
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。
六、算法分析
1、时间复杂度
首先直接插入排序是一个稳定的排序算法；最好的情况下，也就是排序本身是有序的，共需比较n-1次，因为没有移动的记录，时间复杂度为O(n)。最坏的情况下，即排序表是逆序的情况，时间复杂为O（n²）。
2、空间复杂度
算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数。在直接插入排序中只使用了i,j,temp这三个辅助空间单元，所以空间复杂度是O(1)。
