1 插入排序算法定義
插入排序，一般也被稱為直接插入排序。對于少量元素的排序，它是一個有效的算法 。插入排序是一種最簡單的排序方法，它的基本思想是將一個記錄插入到已經(jīng)排好序的有序表中，從而一個新的、記錄數(shù)增1的有序表。在其實(shí)現(xiàn)過程使用雙層循環(huán)，外層循環(huán)對除了第一個元素之外的所有元素，內(nèi)層循環(huán)對當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動。（摘自百度百科）
簡單理解就是類似摸撲克牌的一個過程
2 插入排序詳細(xì)過程
假定有一個數(shù)組：
int[] nums = new int[]{2, 4, 5, 1, 3, 6};
現(xiàn)在需要把它變?yōu)榈剐蚺判颉?/p>
倒敘排序代碼如下：
詳細(xì)排序過程如下：
第一次比較，由于nums[1]小于nums[0],直接跳到break，結(jié)果為
[4, 2, 5, 1, 3, 6]
第二次比較，nums[2]=5大于nums[1]=2, 5和2交換位置，結(jié)果為: [4,5, 2, 1, 3, 6],這時由于j的值為1，所以會再執(zhí)行一次子循環(huán)，這時nums[1]=5大于nums[0]=4，所以4和5交換位置，這時j的值為0，循環(huán)終止。結(jié)果為
[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 插入排序時間復(fù)雜度
由上述代碼可以看到，算法的核心是元素比較和元素交換，因此，算法的復(fù)雜度即為元素比較次數(shù)和元素交換次數(shù)的總和。
元素比較次數(shù)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
元素交換次數(shù)M為比較次數(shù)的三倍：
M=(5+4+3+2+1)*3=((n-1)+(n-2)+...+2+1)*3=3(n^2)/2-3n/2=(3n*(n-1))/2
相加之后的結(jié)果S為：
S=(4n*(n-1))/2=2N^2-2N=O(n^2)
插入排序的時間復(fù)雜度為O(n^2)
不明白時間復(fù)雜度如何得來的參考另外一篇文章（時間復(fù)雜度O(n)是如何得來的？）
4 結(jié)語
感謝各位的閱讀，如有問題，歡迎大家留言反饋，我會在第一時間修正。
如果覺得文章還可以的話，不妨點(diǎn)個關(guān)注吧！??！
