浙江大學-數據結構-簡單排序-9.1.3

簡單排序

插入排序，插入排序可以理解為，如果你會打牌的話，理解為怎麼抓一手牌，這個順序，比如說我第一張牌摸進來,是J,然後第二張牌摸進來是K,一般來說我們把K放到J的後面，因為我們覺得K要J大，第三張牌進來的時候，它是A,那麼我們怎麼做呢？就是A跟K比，我需要跟J比嗎？不需要跟J比，因為我發現它比K大，所以它直接就放在K的後面了，那下一張牌進來的時候，如果是Q,那張牌進來以後，我們該怎麼辦呢？我們要做的是將K,A兩張牌往後錯一下，空一個位置出來，

讓這張新的牌插入，那這是一個什麼樣的過程呢？實際上我在把Q插進來之前，我把它跟A比了一下，它比A要小，所以應該排在A前面的，於是A這張牌要往後錯一位，它又比K小，K也得往後錯一位，然後它發現它比J要大，好了,J不用錯位了，這個空位就是它的，這就是插入排序的一個過程，那最壞情況是什麼呢，就是在這個情況下，我插進來下一張牌是10，我得把4張牌一個一個向後錯位，然後把最前面的位置空出來，10插進去，那麼我們的插入排序呢，其實就可以把它理解為整個抓一手牌的過程，

循環是從第一張牌開始，循環到最後一張，為什麼不是從第0張牌呢？我們不是從0開始記號的嗎？沒有必要，我們假設一開始的時候第0張牌已經在我們手裡面了，然後我需要從下一張牌開始摸進來，摸了下一張牌，放在臨時的位置上，然後我要這麼做呢？我要跟手裡現在有的牌一一對比，要從哪比起呢？要從最後一張牌往前比，所以我有這樣一個for循環，是從當前最後一張牌的位置，開始減減，開始往前比，一直到它等於0，比到最前面那張牌為止，比的時候會是怎麼一個比法呢？只要我手裡這張牌比現在這張牌要小，那麼就應該怎麼辦？現在的這張牌，就應該往後錯位，什麼叫往後錯位呢？也就是把A[i-1]這張牌要存到A[i]的位置上去，也就是把這張牌向後移了一位，一直不停的重複這個過程，直到什麼時候為止呢？直到說我手裡這張牌是大於等於現在這張牌了，就像我剛才插Q進去的時候，發現Q已經大於J了，那麼這個時候就停止，停止跳出這個for循環的時候，那這個i所指的位置就是我手裡這張牌應該放的空位置，那這叫新牌落位，這就是插入排序的過程，其實對於插入排序，最好的情況其實跟冒泡排序其實是一樣的，就是一開始進來的時候，那個牌就是按順序摸的，我先摸了一張10，然後我摸了一張J,去跟10比的時候，發現比它大，所以什麼都不用動，我就直接放在後面了，下一張牌總比最後那張牌大，然後它就順序的放在後面了，那在這種情況下呢，一張牌都不需要移動，但是我仍然需要把所有的牌都摸上來，所以最好情況呢，是一開始就是順序的，那我只需要O(N)的時間把所有的牌都摸進來就好了，最壞是什麼情況呢？我摸的第一張牌是A,第二張牌是K,所以我要把A往後錯一位，第三張牌是Q，所以我得把這兩張牌全部往後錯一位，每摸進一張牌，它都需要把前面所有的牌向後錯一位，那這個是什麼情況呢，就是初始的情況是完全逆序的情況，那麼我們每一次循環，這裡面所有的牌都需要往後錯一位，然後一共做了N-1次循環，所以整體來說時間複雜度是O(N^2)這個數量級的，那我們說插入排序的好處也是這個程序非常短，看上去非常的簡單，而且它比冒泡排序好在哪呢？冒泡排序是兩兩交換，兩兩元素互換的時候，它要涉及到3步，插入排序其實是每個元素往後錯，最後一次性的放在空位裡面去，它會省很多的步驟，但是這其實不是插入排序存在的主要原因了，它有更好的性質，這個我們後面再說，因為我們是在當手裡這張牌嚴格的比前面這張牌小的時候，我們才移位的，如果它們相等的話，這個位置是不動的，這樣也就保證了插入排序這個演算法它也是穩定的，

好，那介紹到這裡呢，我們先來看一個很小的例子，

冒泡排序和插入排序都是需要9次交換才能完成。