插入排序算法解析 _插入排序

1 插入排序算法定义插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。（摘自百度百科）
简单理解就是类似摸扑克牌的一个过程

文章插图

2 插入排序详细过程假定有一个数组：
int[] nums = new int[]{2, 4, 5, 1, 3, 6};现在需要把它变为倒序排序。
倒叙排序代码如下：

文章插图

详细排序过程如下：
第一次比较，由于nums[1]小于nums[0],直接跳到break，结果为
[4, 2, 5, 1, 3, 6]
第二次比较，nums[2]=5大于nums[1]=2, 5和2交换位置，结果为: [4,5, 2, 1, 3, 6],这时由于j的值为1，所以会再执行一次子循环，这时nums[1]=5大于nums[0]=4，所以4和5交换位置，这时j的值为0，循环终止。结果为
[5, 4, 2, 1, 3, 6]
以此类推。。。
[5, 4, 2, 1, 3, 6]
[5, 4, 3, 2, 1, 6]
[6, 5, 4, 3, 2, 1]
3 插入排序时间复杂度由上述代码可以看到，算法的核心是元素比较和元素交换，因此，算法的复杂度即为元素比较次数和元素交换次数的总和。
元素比较次数C为：
C=5+4+3+2+1=(n-1)+(n-2)+...+2+1=(1+(n-1)) * ( (n-1)/2 )=(n^2)/2-n/2=(n*(n-1))/2
元素交换次数M为比较次数的三倍：
M=(5+4+3+2+1)*3=((n-1)+(n-2)+...+2+1)*3=3(n^2)/2-3n/2=(3n*(n-1))/2
相加之后的结果S为：
S=(4n*(n-1))/2=2N^2-2N=O(n^2)
插入排序的时间复杂度为O(n^2)
不明白时间复杂度如何得来的参考另外一篇文章（时间复杂度O(n)是如何得来的？）
4 结语感谢各位的阅读，如有问题，欢迎大家留言反馈，我会在第一时间修正。
如果觉得文章还可以的话，不妨点个关注吧！！！

【插入排序算法解析】