插入排序就是每一步都將一個(gè)待排數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)中的適當(dāng)位置唱蒸，直到全部插入完畢邦鲫。 插入排序方法分直接插入排序和折半插入排序兩種。
詳細(xì)代碼請(qǐng)參考Algorithm。參考代碼比文字好理解庆捺。
時(shí)間復(fù)雜度與空間復(fù)雜度
時(shí)間復(fù)雜度：O（n^2)
空間復(fù)雜度：O（1）
最少比較次數(shù)：（已排序的數(shù)組）n-1次
最多比較次數(shù)：（降序的數(shù)組）n(n-1)/2次
數(shù)組在已排序或者是“近似排序”時(shí)古今，插入排序效率的最好情況運(yùn)行時(shí)間為O(n)；插入排序最壞情況運(yùn)行時(shí)間和平均情況運(yùn)行時(shí)間都為O（n^2) 滔以。
插入排序不適合對(duì)大量數(shù)據(jù)排序捉腥，適合對(duì)接近排序的數(shù)據(jù)排序。插入排序是穩(wěn)定排序你画。通常抵碟，插入排序呈現(xiàn)出二次排序算法中的最佳性能。對(duì)于具有較少元素（如n<=15）的列表來(lái)說(shuō)坏匪，二次算法十分有效拟逮。在列表已被排序時(shí)，插入排序是線性算法O(n)适滓。在列表“近似排序”時(shí)敦迄，插入排序仍然是線性算法。在列表的許多元素已位于正確的位置上時(shí)凭迹，就會(huì)出現(xiàn)“近似排序”的條件罚屋。
算法描述
假定n是數(shù)組的長(zhǎng)度，首先假設(shè)第一個(gè)元素被放置在正確的位置上嗅绸，這樣僅需從1到n-1范圍內(nèi)對(duì)剩余元素進(jìn)行排序脾猛。對(duì)于每次遍歷，從0到i-1范圍內(nèi)的元素已經(jīng)被排好序鱼鸠，每次遍歷的任務(wù)是：通過(guò)掃描前面已排序的子列表猛拴，將位置i處的元素定位到從0到i的子列表之內(nèi)的正確的位置上。
將arr[i]復(fù)制為一個(gè)名為target的臨時(shí)元素瞧柔。向下掃描列表漆弄，比較這個(gè)目標(biāo)值target與arr[i-1]、arr[i-2]的大小造锅，依次類推。這個(gè)比較過(guò)程在小于或等于目標(biāo)值的第一個(gè)元素(arr[j])處停止廉邑，或者在列表開(kāi)始處停止（j=0）哥蔚。在arr[i]小于前面任何已排序元素時(shí)，后一個(gè)條件（j=0）為真蛛蒙，因此糙箍，這個(gè)元素會(huì)占用新排序子列表的第一個(gè)位置。在掃描期間牵祟，大于目標(biāo)值target的每個(gè)元素都會(huì)向右滑動(dòng)一個(gè)位置（arr[j]=arr[j-1]）深夯。一旦確定了正確位置j，目標(biāo)值target（即原始的arr[i]）就會(huì)被復(fù)制到這個(gè)位置。與選擇排序不同的是咕晋，插入排序?qū)?shù)據(jù)向右滑動(dòng)雹拄，并且不會(huì)執(zhí)行交換。
