文中大部分內(nèi)容為摘抄自網(wǎng)友文章悬蔽，只供個(gè)人學(xué)習(xí)和備忘谚咬。
算法思想
插入排序的基本思想是：每步將一個(gè)待排序的記錄竞端，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上椅棺，直到全部插入完為止屁擅。
也可理解為：將一個(gè)記錄插入到已排序好的有序表中偿凭，從而得到一個(gè)新的記錄數(shù)增1的有序表。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列派歌，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入弯囊，直至整個(gè)序列有序?yàn)橹埂?br>
要點(diǎn)：設(shè)立哨兵，作為臨時(shí)存儲(chǔ)和判斷數(shù)組邊界之用胶果。
算法步驟
⒈ 從有序數(shù)列和無(wú)序數(shù)列{a2,a3匾嘱，…，an}開始進(jìn)行排序早抠；
⒉ 處理第i個(gè)元素時(shí)（i=2,3霎烙，…，n）蕊连，數(shù)列{a1,a2悬垃，…，ai-1}是已有序的甘苍，而數(shù)列{ai,ai+1尝蠕，…，an}是無(wú)序的载庭。用ai與ai-1看彼，a i-2，…囚聚，a1進(jìn)行比較靖榕，找出合適的位置將ai插入；
⒊ 重復(fù)第二步顽铸，共進(jìn)行n-i次插入處理茁计，數(shù)列全部有序。
算法復(fù)雜度
如果目標(biāo)是把n個(gè)元素的序列升序排列谓松，那么采用插入排序存在最好情況和最壞情況簸淀。
- 最好情況就是瓶蝴，序列已經(jīng)是升序排列了，在這種情況下租幕，需要進(jìn)行的比較操作需（n-1）次即可。
- 最壞情況就是拧簸，序列是降序排列劲绪，那么此時(shí)需要進(jìn)行的比較共有n(n-1)/2次。
- 插入排序的賦值操作是比較操作的次數(shù)加上 (n-1）次盆赤。平均來(lái)說(shuō)插入排序算法的時(shí)間復(fù)雜度為O(n^2）贾富。
- 因而，插入排序不適合對(duì)于數(shù)據(jù)量比較大的排序應(yīng)用牺六。但是颤枪，如果需要排序的數(shù)據(jù)量很小，例如淑际，量級(jí)小于千畏纲，那么插入排序還是一個(gè)不錯(cuò)的選擇。
算法穩(wěn)定性
插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上春缕，一次插入一個(gè)元素盗胀。當(dāng)然，剛開始這個(gè)有序的小序列只有1個(gè)元素锄贼，就是第一個(gè)元素票灰。比較是從有序序列的末尾開始，也就是想要插入的元素和已經(jīng)有序的最大者開始比起宅荤，如果比它大則直接插入在其后面屑迂，否則一直往前找直到找到它該插入的位置。如果碰見(jiàn)一個(gè)和插入元素相等的冯键，那么插入元素把想插入的元素放在相等元素的后面惹盼。所以，相等元素的前后順序沒(méi)有改變琼了，從原無(wú)序序列出去的順序就是排好序后的順序逻锐，所以插入排序是穩(wěn)定的。
算法描述（JAVA）
public void insertSort(int arr[]) {
for(int i= 1; i<arr.length; i++){
if(arr[i] < arr[i-1]){//如果小于前一位雕薪，開始定位插入位置
int j = i-1; //標(biāo)記開始后移的位置
int temp = arr[i]; //臨時(shí)存儲(chǔ)待插入數(shù)據(jù)
while(j > -1 && temp < arr[j]){ //遍歷定位位置同時(shí)向后移動(dòng)
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
}
