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 結語

感謝各位的閱讀，如有問題，歡迎大家留言反饋，我會在第一時間修正。

如果覺得文章還可以的話，不妨點個關注吧！！！