排序算法經過了很長時間的演變，產生了很多種不同的方法。對于初學者來說，對它們進行整理便于理解記憶顯得很重要。每種算法都有它特定的使用場合，很難通用。因此，我們很有必要對所有常見的排序算法進行歸納。
我不喜歡死記硬背，我更偏向于弄清來龍去脈，理解性地記憶。比如下面這張時間復雜度圖，我們將圍繞這張圖來分析。
上面的這張圖來自一個PPT。它概括了數據結構中的所有常見的排序算法，給大家總結如下。
區分穩定與不穩定：快速、希爾、堆、選擇不穩定，其他排序算法均穩定。
平均時間復雜度：冒泡，選擇，插入是O(n2)，其他均是O(n*log2n)
最壞時間復雜度：冒泡，選擇，插入，快排是O(n2)，其他是O(n*log2n)
平均和最壞時間復雜度：只有O(n2)和O(n*log2n)兩種，冒泡，選擇，插入是O(n2)，最壞情況下加一個快排，其他均是O(nlog2n)。
一、直接插入排序(插入排序)。
1、算法的偽代碼(這樣便于理解)：