插入排序時(shí)一種常見(jiàn)的排序算法，有點(diǎn)類似于我們打撲克摸牌的過(guò)程，每摸一張牌，我們便通過(guò)對(duì)比手上已有的牌，將剛拿到的牌放入合適的位置。
實(shí)現(xiàn)實(shí)現(xiàn)思路
假設(shè)前j-1個(gè)元素已經(jīng)排好序， 將第j個(gè)元素分別于其前面元素[i]比較,
- 如i元素較大，則將i元素的值往前移動(dòng)一位，即 a[i+1] = a[i]
- 若i元素較小，則直接將j位置的值放到 i+1元素的位置。
下面以[1, 5, 3, 4, 5, 6, 8]這個(gè)待排序數(shù)組為例，以圖解的方式來(lái)講解一下插入排序的具體過(guò)程。
從j等于1開(kāi)始(這里假設(shè)初始位置為0)，如下圖所示
此時(shí)拿著5和前面的每個(gè)數(shù)對(duì)比，此處是1，發(fā)現(xiàn) 5 > 1,故將五放在 i+1的位置，即5的位置保持不變，此時(shí)i = 0, 即前面已經(jīng)沒(méi)有其他數(shù)了了，所以前兩個(gè)數(shù)已經(jīng)排好序。
接著 j = j+ 1,如下圖所示。 i = j-1
為了能將3排好序，必須將其與其前面（位置0,1）的數(shù)逐個(gè)對(duì)比，這里先對(duì)比 3和5，發(fā)現(xiàn) 3< 5,此時(shí) 將5放到3的位置，
此時(shí)i =0, 對(duì)比i位置的值和key的大小，發(fā)現(xiàn) 1 < 3,此時(shí)找到key應(yīng)該放置的位置，即 i + 1 =3;
此時(shí)前三個(gè)數(shù)已經(jīng)排好序，j 繼續(xù)加1
此時(shí)，要將 key =4 插入到前面( 0 -3)的合適位置中去，同樣對(duì)比 key和 i位置的值，發(fā)現(xiàn) 5 > 4,大的應(yīng)該往后推，所以 5應(yīng)該在4的后面。
這里將5往前移動(dòng)一位， i –,在比較 i位置的值和 key的大小關(guān)系
發(fā)現(xiàn) 3 < key，0 -i都已排好序，所以找到了key的合適位置，即是 i+ 1;
j繼續(xù)加1，重復(fù)上述過(guò)程，直至 j = 6,最后便可以排成
1，3, 4，5, 5，6， 8
簡(jiǎn)而言之，每次排序一個(gè)數(shù)key，都要對(duì)比前面的對(duì)比該位置的值與該位置前面的值的大小，若key較小，則將與key對(duì)比的數(shù)往后( i+1)移動(dòng)一位。直到找到一個(gè)小于或等于key的值，則將key放在該數(shù)的后一個(gè)位置處。
根據(jù)上面的過(guò)程，我們可以很容易的得到該排序過(guò)程的時(shí)間復(fù)雜度，因?yàn)橐判蛎恳粋€(gè)數(shù)(n),排序該數(shù)的時(shí)候，還得將這個(gè)數(shù)與前面最多(n-1)個(gè)數(shù)對(duì)比，才能找到合適的位置。所以其時(shí)間復(fù)雜度約為0(n2)。
js代碼實(shí)現(xiàn)
總結(jié)
1)從第二位開(kāi)始,與前面的所有數(shù)值比較,將大的數(shù)據(jù)向下移動(dòng)
2)時(shí)間復(fù)雜度是O(n2)
