之前我们说过了冒泡排序,现在我们再来看一个经常和冒泡排序拿出来比较的排序算法插入排序,为什么要学习数据模型和算法,为什么有现成的轮子还要自己再动手去写等等,这些问题的原因我都写在这里面了,欢迎大家批评斧正。 插入排序老规矩,学习算法三板斧。 第一斧:学习其原理思想插入排序我们可以将整个数组看做两个区间,分别是已排序区间和未排序区间。百度百科中对插入排序的基本思想描述如下:
看明白了吗?如果没有看明白也没有关系,我们可以举一个具体的例子,画图看看。 第二斧:“举例+画图”理解思想我们来举个例子,假设我们手头有一个int类型的数组a,它包含的元素为8 7 1 2 3 6 9
那按照插入排序的思想,将数组分为两个区间,一个是已经排序的另外一个是没有排序的。很显然目前这个数组肯定是完全没有排序的,那么我们是否可以这么理解,当前这个数组结构的已排序区间为【】未排序区间为【8,7,1,2,3,6,9】。那我们仅需要将未排序区间内的元素逐个插入到已排序的区间内就好啦。 还有点晕吗?那来吧,遇事不决就画图(图中红色的部分代表已排序区间,黄色的部分代表未排序区间): 我们跟着图来看一下插入排序的过程是怎么样的。 第一次插入的时候,将未排序区间中的第一个元素8插入了已排序区间中,因为这个时候已排序区间中没有元素,所以这里就相当于自旋了一下,并没有实际的发生插入操作。 第二次插入的时候,将未排序区间中的第一个元素7插入了已排序区间中,开始从已排序区间的第0位开始遍历,那已排序区间的第0位是8。那7>8,所以将7插入到8的前面 依次类推指导未排序区间中一个元素都没有了。 第三斧:show me the code到现在位置大家已经看完了插入排序的原理和流程了,相信大家在脑海中对插入排序都有一个大概的认识了,那我们现在趁着印象很深,都动手写一个插入排序算法。
学习算法其实没啥诀窍,最简单就是最笨的办法,就是多看原理然后多写代码。如果后面你可以比着你自己画的图写出代码实现功能,就已经入门啦~ |
|
来自: 昵称70680357 > 《待分类》