????????前兩種算法原理和實(shí)現(xiàn)都相對(duì)簡單，而到了插入排序開始，就會(huì)有一點(diǎn)小小的繞。（我當(dāng)初也暈了(|3」∠)）插入排序的原理不難，每次選擇一個(gè)數(shù)插入到前面他應(yīng)該在的位置上。原理很簡單hhh但是實(shí)現(xiàn)有點(diǎn)小繞。我們同樣的一組測試用例：[5,3,8,6,9,2,1,4,7]，利用Excel表格能更好的看到效果。

我們舉個(gè)栗子，在第一遍遍歷時(shí)的設(shè)置初始下標(biāo)i=1，j=i-1,nums[i]此時(shí)值為3，j=0，那么此時(shí)nums[j]的值比nums[i]大，因此，nums[i]應(yīng)該插入到nums[j]的前面！說明有序時(shí)nums[i]的位置應(yīng)該在更前面，所以我們先把nums[i]記錄下來，把j往后面挪，令nums[j+1]=nums[j]，而j繼續(xù)向前，直到遍歷到開頭或者遇到nums[i]比nums[j]大的時(shí)候，這時(shí)的位置就是nums[i]該插入的位置了。

我們來看一下實(shí)現(xiàn)的代碼：

打印一下每遍運(yùn)行的結(jié)果看一下。

由每次的循環(huán)我們可以看到，每一次遍歷都會(huì)多出一個(gè)數(shù)插入到前面他應(yīng)到的位置上。

時(shí)間復(fù)雜度：O(n^2)，空間復(fù)雜度：O(1)

優(yōu)點(diǎn)：在最好的情況下時(shí)間復(fù)雜度為O(n)，與冒泡排序一樣。但是在處理大量數(shù)據(jù)時(shí)，還記不記得我們是怎么處理冒泡排序中的值的？沒錯(cuò)，交換！而一次交換需要耗費(fèi)3條語句，插入排序只需要一次賦值即可。因此在同樣的情況下，插入排序的處理時(shí)間會(huì)優(yōu)于冒泡排序。
缺點(diǎn)：同樣的，在最差的條件下（比如我們要求正序但用例是完全倒序），時(shí)間復(fù)雜度為O(n^2)。