前言：前兩天騰訊筆試受到1萬點暴擊，感覺浪費我兩天時間去?？途W做題……這篇博客介紹幾種簡單/常見的排序算法，算是整理下。

時間復雜度

（1）時間頻度一個算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

（2）時間復雜度在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什么規律。為此，我們引入時間復雜度概念。 一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n))為算法的漸進時間復雜度，簡稱時間復雜度。

指數時間

指的是一個問題求解所需要的計算時間m(n)，依輸入數據的大小而呈指數成長（即輸入數據的數量依線性成長，所花的時間將會以指數成長）

for (i=1; i<=n; i++) x++;for (i=1; i<=n; i++) for (j=1; j<=n; j++) x++;

第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個算法的時間復雜度為Ο(n+n2)=Ο(n2)。

常數時間

若對于一個算法的上界與輸入大小無關，則稱其具有常數時間，記作時間。一個例子是訪問數組中的單個元素，因為訪問它只需要一條指令。但是，找到無序數組中的最小元素則不是，因為這需要遍歷所有元素來找出最小值。這是一項線性時間的操作，或稱時間。但如果預先知道元素的數量并假設數量保持不變，則該操作也可被稱為具有常數時間。

對數時間

若算法的T(n) =O(logn)，則稱其具有對數時間

常見的具有對數時間的算法有二叉樹的相關操作和二分搜索。

對數時間的算法是非常有效的，因為每增加一個輸入，其所需要的額外計算時間會變小。
遞歸地將字符串砍半并且輸出是這個類別函數的一個簡單例子。它需要O（log n）的時間因為每次輸出之前我們都將字符串砍半。 這意味著，如果我們想增加輸出的次數，我們需要將字符串長度加倍。

線性時間

如果一個算法的時間復雜度為O(n)，則稱這個算法具有線性時間，或O(n)時間。非正式地說，這意味著對于足夠大的輸入，運行時間增加的大小與輸入成線性關系。例如，一個計算列表所有元素的和的程序，需要的時間與列表的長度成正比。