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 结语

感谢各位的阅读，如有问题，欢迎大家留言反馈，我会在第一时间修正。

如果觉得文章还可以的话，不妨点个关注吧！！！