用圖說(shuō)話
插入排序圖解
放碼過(guò)來(lái)C++
// 插入排序
void insertionSort(vector<int> array)
{
/*
算法思想：根據(jù)插入排序的思想，將數(shù)組分成兩個(gè)部分，一個(gè)是有序一個(gè)是待插入狞甚，
然后拿待插入的每一個(gè)元素去跟有序數(shù)組的每一個(gè)元素比較
ok，這里就有大概的思路了演痒，拿待插入的每一個(gè)元素，那我這里得用一個(gè)循環(huán)來(lái)遍歷
跟有序數(shù)組的每一個(gè)元素比較，這里還得一個(gè)循環(huán)來(lái)遍歷有序數(shù)組
那么我腦海中大概的代碼就是醬紫了
for(待插入的數(shù)組) {
for(有序數(shù)組) {
處理待插入和有序數(shù)組的比較的
}
}
ok伪嫁，有了這個(gè)思路后漩氨，我們就開(kāi)始一步一步擼短条，慢慢調(diào)了
*/
// *** 開(kāi)始擼,對(duì)著我做的圖來(lái)看比較容易理解哦！ ***/
// 遍歷待插入數(shù)組才菠；
// 之所以i從1開(kāi)始茸时，是因?yàn)槟J(rèn)數(shù)組的第一個(gè)元素的有序的
for (int i=1; i<array.size(); i++) {
// 取待插入數(shù)組的第一個(gè)元素
// i表示待插入數(shù)組的第一個(gè)元素下標(biāo)
// kmp表示待插入數(shù)組的第一個(gè)元素
int kmp = array[i];
// i-1 就是有序數(shù)組的最后一個(gè)元素
int j = i-1; // 為什么要設(shè)置這個(gè)j呢，因?yàn)橄旅嬗衱hile() 要把這個(gè)j作為循環(huán)的終止條件
// 當(dāng)待插入元素kmp小于有序數(shù)組的最后一個(gè)元素時(shí)赋访，這個(gè)有序數(shù)組的最后一個(gè)元素后移
// kmp即將要插入的值
// 為什么j>=0 因?yàn)楸热? 3 4 2其中9 3 4 是有序數(shù)組可都，2是即將要插入的值缓待，那么這時(shí)候2跟9比較
// 也就是kmp = 2 Array[j] == 9，則j == 0渠牲；所以j == 0是要進(jìn)入循環(huán)的旋炒，所以j>=0
// 這個(gè)while循環(huán)的作用就是拿待插入值跟有序數(shù)組元素一一比較，然后大于就讓有序數(shù)組的元素后移签杈，最后將要插入值的位置空出來(lái)
while (j>=0 && kmp<array[j]) {
// 后序數(shù)組元素后移
array[j+1] = array[j];
j--;
}
// 當(dāng)比較完之后瘫镇，將這個(gè)即將插入的值kmp，插入到指定的數(shù)組位置中
array[j+1] = kmp;
// 為什么是j+1 舉個(gè)例子
// 比如9 3 4 2其中9 3 4 是有序數(shù)組答姥，2是即將要插入的值铣除，那么這時(shí)候2跟9比較
// 也就是(kmp == 2) < (array[j==0] == 9) 那么滿足條件，進(jìn)入循環(huán)鹦付，進(jìn)入之后尚粘，9后移，j--敲长，這時(shí)候j--后就等于-1了
// 所以我這個(gè)即將要插入的值kmp郎嫁，應(yīng)該插入下標(biāo)為0的位置，但是這時(shí)候的j==-1祈噪，所以array[j+1] = kmp
}
}
