最近想验证下自己的算法基础，发现算法和数据结构真的是程序员的内功的一个修炼，不仅考验思维逻辑还考验了一个人对数据结构的理解程度，我记得老师从开始编程的第一天就告诉我们，算法和数据结构是每一个程序员必须经历的阶段，很多人在实际工作中并没有使用到算法，所以都忽略了这一个非常重要的东西，那我接下结合代码来聊聊自己的对算法的理解。
插入排序，顾名思义就是将数据按照指定的顺序进行排序，怎么理解呢？我个人习惯将插入排序理解“斗地主”中的牌，如果我们手中有一个顺子，这时候刚起完牌，顺子的顺序是648573，如果打牌的人都会习惯性的将牌按照大小进行整理(至少我是这样的，可能强迫症吧)，这个时候我们不断的抽牌，插入正确的位置，这就可以模拟我们今天要讲的插入排序。
接下来，我们会按照标注的一步一步来解析，首先看代码图中标注1，插入排序的核心思想就是每次要插入的数都要对原来已经排序好的序列进行重新排序，这是什么意思呢，看步骤图第三步，此步骤是对5进行插入，可以看到首先5跟8对比，5比8小，5向前移一位，此时顺序是465873，这个时候插入并没有完成，因为在5之前已经排序好的序列是468，而按照上述核心思想来，5会继续跟6去对比，然后5向前移一位，此时顺序是456873，此时5还会与4对比，注意，请看代码3标注，怎么判断完成？出现一个最小数字或者达到最左端，4比5小，此时5的插入完成了。那么标注2怎么解释呢？看步骤图，原始数据的时候，我们拿6作为已经完成排序的序列，步骤一种我们拿46作为已经排序好的序列，步骤二中我们拿468作为已经排序好的序列，步骤三种我们拿4568作为已经排序好的序列，步骤四中我们拿45678作为已经排序好的序列。那么标注4是什么意思呢？4的意思就是我们需要插入的数据都是在标注3中的序列的后面一个数就是我们将要插入的数字。举一个例子，在步骤图中第三步，已经排好的序列是4568，接下我们要插入的就是7.
标注5------->遍历我们模拟的数组，目的插入排序数组元素
注意 temp中储存的是我们要插入的数字
标注6-------->遍历插入的数在原数据位置之前已经排序好的序列 举例 看步骤四，此时插入数字是7，在原数据中位置之前已排好序的序列就是4568
标注7--------->将插入的数与已经排序好的序列中的元素比较，若小。则插入的数向前移一位
标注8---------->将我们要插入的数放到正确的位置，举个例子，继续看步骤图中的第四步，此时插入的数是7,7的索引此时是4，而此时j的值是3,而7与8比较，7<8,7向前移一位，7取代了8原有的位置，此时7的索引还是4；那么肯定有人问我，这个j到底指什么？其实这个j就是要插入的数与前面已经排好序的序列比较中刚好比最后一个数大的这个数的位置。
这个时间复杂度是O（N²），所以不适合数据较大的排序
好了，这个插入排序就分析到这里，其实算法需要写出来，然后debug一步步来验证，然后消化理解，这个需要长期的积累逻辑思想。
网友评论