博客

接下来我来讲述一下插入排序法。

首先来解释一下插入排序法的原理，它的原理是每插入一个数都要将它和之前的已经完成排序的序列进行重新排序，也就是要找到新插入的数对应原序列中的位置。那么也就是说，每次插入一个数都要对原来排序好的那部分序列进行重新的排序，时间复杂度同样为O(n²)。 这种算法是稳定的排序方法。

直接插入排序算法分析

根据代码我们来解释一下直接插入排序的核心

例如，我们要对5,3,4,6,2这几个数进行排序

当这个数组进入函数后，下标首先定义到i = 1，即排序前，首先定义为a[0] = 5即是有序的。

进入循环内，比较a[1] 是否小于 a[0] 发现是小于的，这个时候按理说是要把a[0]这个元素右移动1位。然后将a[1]这个元素插在a[0]的位置上

但是考虑到这样子将覆盖原来的a[1]的值，所以先将a[1]的值拷贝一份给temp，然后将a[0]右移一位，再将temp的值传给a[0] .即

这时i =2了。此时a[0],a[1]属于有序的序列了，我们此时再次比较a