19.9 插入排序與選擇排序

考卷很愛給你一段排序程式碼，再問「跑完第幾輪的時候，陣列長什麼樣子」。11.10 的泡沫排序是其中一種，另外兩位常客是插入排序與選擇排序。三種的規則都只有一句話，抓住那句話就追得動整張表。

下面兩支程式都拿同一組資料 5, 2, 4, 1, 3 開場，每跑完一輪就把整個陣列印出來，方便左右對照。

¶插入排序：把手上這張牌往前插

規則：從左邊第二個數開始，每個數往前找到自己該待的位置插進去。就像打撲克牌整理手牌——新抽到的牌往左邊一張一張比，比它大的通通往右讓一格，讓出來的縫隙就是它的位置。左邊那一段永遠是排好的。