图解插入排序算法

2022-04-06 插入排序

插入排序时一种常见的排序算法，有点类似于我们打扑克摸牌的过程，每摸一张牌，我们便通过对比手上已有的牌，将刚拿到的牌放入合适的位置。实现实现思路假设前j-1个元素已经排好序，将第j个元素分别于其前面元素[i]比较,

如i元素较大，则将i元素的值往前移动一位，即 a[i+1] = a[i]
若i元素较小，则直接将j位置的值放到 i+1元素的位置。

下面以[1, 5, 3, 4, 5, 6, 8]这个待排序数组为例，以图解的方式来讲解一下插入排序的具体过程。
从j等于1开始(这里假设初始位置为0) ，如下图所示

文章插图

此时拿着5和前面的每个数对比，此处是1 ，发现 5 > 1,故将五放在 i+1的位置，即5的位置保持不变，此时i = 0, 即前面已经没有其他数了了，所以前两个数已经排好序。
接着 j = j+ 1,如下图所示。i = j-1

文章插图

为了能将3排好序，必须将其与其前面（位置0,1）的数逐个对比，这里先对比 3和5 ，发现 3< 5,此时将5放到3的位置，

文章插图

此时i =0, 对比i位置的值和key的大小，发现 1 < 3,此时找到key应该放置的位置，即 i + 1 =3;

文章插图

此时前三个数已经排好序， j 继续加1

文章插图

此时，要将 key =4 插入到前面( 0 -3)的合适位置中去，同样对比 key和 i位置的值，发现 5 > 4,大的应该往后推，所以 5应该在4的后面。

文章插图

这里将5往前移动一位， i –,在比较 i位置的值和 key的大小关系
发现 3 < key ， 0 -i都已排好序，所以找到了key的合适位置，即是 i+ 1;

文章插图

j继续加1 ，重复上述过程，直至 j = 6,最后便可以排成
1 ， 3, 4 ， 5, 5 ， 6 ， 8
简而言之，每次排序一个数key ，都要对比前面的对比该位置的值与该位置前面的值的大小，若key较小，则将与key对比的数往后( i+1)移动一位。直到找到一个小于或等于key的值，则将key放在该数的后一个位置处。
根据上面的过程，我们可以很容易的得到该排序过程的时间复杂度，因为要排序每一个数(n),排序该数的时候，还得将这个数与前面最多(n-1)个数对比，才能找到合适的位置。所以其时间复杂度约为0(n2) 。
js代码实现

文章插图

总结1)从第二位开始,与前面的所有数值比较,将大的数据向下移动
2)时间复杂度是O(n2)

【图解插入排序算法】

推荐阅读

上一篇：PHP中常见的五种设计模式

下一篇：从抵押到放款要几天从抵押登记到放款要几天2022