一文搞定十大排序算法（動畫圖解）

排序算法是測試開發(fā)技術(shù)面試中的常考題目
，本文用動畫圖解面試必會十大排序算法，由淺入深 、形象記憶，再也忘不掉。

排序基礎(chǔ)知識

排序的定義

排序 ，就是重新排列表中的元素，使表中的元素滿足按關(guān)鍵字遞增或遞減的過程。為了査找方便，通常要求計算機中的表是按關(guān)鍵字有序的 。

排序的確切定義如下 ：

輸入: n個記錄 R1，R2，R3…Rn, 對應的關(guān)鍵字為 K1,K2,K3…Kn  輸出: 輸入序列的一個重排R1’
，R2’，R3’…Rn’, 使得有K1’   K2’   K3’…   Kn’ (其中  可以換成其它的比較大小符號)	。

算法的穩(wěn)定性：

若待排序表中有兩個元素 Ri 和 Rj，其對應的關(guān)鍵字 keyi = kcyj , 且在排序前 Ri 在 Rj 的前面
。使用某一排序算法排序后，Ri 仍然在 Rj 的前面盡的前面 ，則稱這個排序算法是穩(wěn)定的。否則稱排序算法是不穩(wěn)定的。

需要注意的是 ，算法是否具有穩(wěn)定性并不能衡量—個算法的優(yōu)劣，它主要針對算法的性質(zhì)進行描述 。只需舉出一組關(guān)徤字的實例，即可說明一個算法是不穩(wěn)定的。

時間復雜度
：[1]（來自百度百科）

算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù) ，用 T(n) 表示 ，若有某個輔助函數(shù) f(n) ，使得 T(n)/f(n) 的極限值（當n趨近于無窮大時）為不等于零的常數(shù)，則稱 f(n) 是 T(n) 的同數(shù)量級函數(shù) 。記作 T(n)=O(f(n)) ，稱 O(f(n)) 為算法的漸進時間復雜度，簡稱時間復雜度。

分析 ：隨著模塊n的增大 ，算法執(zhí)行的時間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小，算法的時間復雜度越低