本文將介紹排序算法中的插入排序，包括：插入排序?qū)嵗?，代碼解析，效率分析。

1 插入排序?qū)嵗?/h2>

今天來學(xué)習(xí)插入排序，在講插入排序之前，我們先來講一講撲克牌。每個人都會打撲克牌，不知道你們有沒有注意到，我們在拿牌的時候，會習(xí)慣性地把手上的牌按照從小到大排好。這樣我們在出牌的時候才不會手忙腳亂。當(dāng)你的小伙伴正在發(fā)牌的時候，如果你習(xí)慣發(fā)一張拿一張，你可能會無意中用到插入排序來完成你的摸牌。

首先，拿到第一張牌，此時不用做任何操作。

拿到第二張牌之后，如果比原來的小，就放在左邊，如果比原來的大，就放在右邊。

拿到第三張牌之后，就找到右邊比這張牌大，左邊比這張牌小的地方插進去。

拿到第四張，第五張……第n張，都是如此。

如果以上是你拿到牌之后的做法，那你已經(jīng)學(xué)會了插入排序，并且在無意中運用到了打牌之中。

插入排序的基本思想，就是每一步將一個待排序的元素，插入到前面已經(jīng)排好序的有序序列中，直到所有元素都插入完畢為止。

是不是跟上面摸牌的過程很像呢？來看一下插入排序的例子：

image

默認第一張牌是有序的，因此插入排序只需要排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 代碼解析

image

14行：插入排序需要n-1趟,從下標i=1開始遍歷

15-22行：變量j初始化為當(dāng)前待插入元素i，并設(shè)置變量temp存儲我們待插入的元素。從后往前找，如果前一個元素j-1比j大，讓前一個元素往后移，覆蓋j的值，并且j自身減1。直到j(luò)<=0(所有元素都比待插入元素大，此時插入到開頭位置)，或者a[j]大于等于a[j-1] (j已經(jīng)到了它應(yīng)該插入的位置，再往前就不是有序數(shù)組了)。跳出wihle循環(huán)后，j已經(jīng)到達它要插入的位置，讓a[j]=temp;即可。

3 效率分析

注意到如果正確的插入位置在中間，需要把它右邊所有的元素后移一個位置，再把元素插入。最差情況下，如果是把一個降序序列排成升序，比如[10,9,8,7,6]，則每次插入元素的位置都是在開頭，每次都需要移動整個有序數(shù)組。其時間復(fù)雜度為O()。