本文將介紹排序算法中的插入排序，包括：插入排序?qū)嵗酰a解析擒贸，效率分析臀晃。
1 插入排序?qū)嵗?/h2>
今天來學(xué)習(xí)插入排序，在講插入排序之前酗宋，我們先來講一講撲克牌积仗。每個(gè)人都會(huì)打撲克牌，不知道你們有沒有注意到蜕猫，我們?cè)谀门频臅r(shí)候寂曹，會(huì)習(xí)慣性地把手上的牌按照從小到大排好。這樣我們?cè)诔雠频臅r(shí)候才不會(huì)手忙腳亂回右。當(dāng)你的小伙伴正在發(fā)牌的時(shí)候隆圆，如果你習(xí)慣發(fā)一張拿一張，你可能會(huì)無意中用到插入排序來完成你的摸牌翔烁。
首先渺氧，拿到第一張牌，此時(shí)不用做任何操作蹬屹。
拿到第二張牌之后侣背，如果比原來的小，就放在左邊慨默，如果比原來的大贩耐，就放在右邊。
拿到第三張牌之后厦取，就找到右邊比這張牌大潮太，左邊比這張牌小的地方插進(jìn)去。
拿到第四張虾攻，第五張……第n張铡买，都是如此。
如果以上是你拿到牌之后的做法霎箍，那你已經(jīng)學(xué)會(huì)了插入排序奇钞，并且在無意中運(yùn)用到了打牌之中。
插入排序的基本思想漂坏，就是每一步將一個(gè)待排序的元素蛇券，插入到前面已經(jīng)排好序的有序序列中，直到所有元素都插入完畢為止樊拓。
是不是跟上面摸牌的過程很像呢纠亚？來看一下插入排序的例子：
默認(rèn)第一張牌是有序的，因此插入排序只需要排n-1趟筋夏。
第一趟蒂胞，把5插入到有序序列[4]中，得到[4,5]条篷。
第二趟骗随，把1插入有序序列[4,5]中蛤织，得到[1,4,5]。
第三趟鸿染，把10插入有序序列[1,4,5]中指蚜，得到[1,4,5,10]。
最后一趟涨椒，把3插入有序序列[1,4,5,10]中摊鸡，得到最終的[1,3,4,5,10]。
2 代碼解析
14行：插入排序需要n-1趟,從下標(biāo)i=1開始遍歷
15-22行：變量j初始化為當(dāng)前待插入元素i蚕冬，并設(shè)置變量temp存儲(chǔ)我們待插入的元素卖词。從后往前找陵霉，如果前一個(gè)元素j-1比j大私蕾，讓前一個(gè)元素往后移穆役，覆蓋j的值，并且j自身減1旁蔼。直到j(luò)<=0(所有元素都比待插入元素大锨苏，此時(shí)插入到開頭位置)，或者a[j]大于等于a[j-1] (j已經(jīng)到了它應(yīng)該插入的位置棺聊，再往前就不是有序數(shù)組了)伞租。跳出wihle循環(huán)后，j已經(jīng)到達(dá)它要插入的位置躺屁，讓a[j]=temp;即可肯夏。
3 效率分析
注意到如果正確的插入位置在中間经宏，需要把它右邊所有的元素后移一個(gè)位置犀暑，再把元素插入。最差情況下烁兰，如果是把一個(gè)降序序列排成升序耐亏，比如[10,9,8,7,6]，則每次插入元素的位置都是在開頭沪斟，每次都需要移動(dòng)整個(gè)有序數(shù)組广辰。其時(shí)間復(fù)雜度為O()。
