前言：前兩天騰訊筆試受到1萬(wàn)點(diǎn)暴擊，感覺(jué)浪費(fèi)我兩天時(shí)間去牛客網(wǎng)做題……這篇博客介紹幾種簡(jiǎn)單/常見(jiàn)的排序算法，算是整理下。

時(shí)間復(fù)雜度

（1）時(shí)間頻度一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度。記為T(mén)(n)。

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

指數(shù)時(shí)間

指的是一個(gè)問(wèn)題求解所需要的計(jì)算時(shí)間m(n)，依輸入數(shù)據(jù)的大小而呈指數(shù)成長(zhǎng)（即輸入數(shù)據(jù)的數(shù)量依線性成長(zhǎng)，所花的時(shí)間將會(huì)以指數(shù)成長(zhǎng)）

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

第一個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n)，第二個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n2)，則整個(gè)算法的時(shí)間復(fù)雜度為Ο(n+n2)=Ο(n2)。

常數(shù)時(shí)間

若對(duì)于一個(gè)算法的上界與輸入大小無(wú)關(guān)，則稱(chēng)其具有常數(shù)時(shí)間，記作時(shí)間。一個(gè)例子是訪問(wèn)數(shù)組中的單個(gè)元素，因?yàn)樵L問(wèn)它只需要一條指令。但是，找到無(wú)序數(shù)組中的最小元素則不是，因?yàn)檫@需要遍歷所有元素來(lái)找出最小值。這是一項(xiàng)線性時(shí)間的操作，或稱(chēng)時(shí)間。但如果預(yù)先知道元素的數(shù)量并假設(shè)數(shù)量保持不變，則該操作也可被稱(chēng)為具有常數(shù)時(shí)間。

對(duì)數(shù)時(shí)間

若算法的T(n) =O(logn)，則稱(chēng)其具有對(duì)數(shù)時(shí)間

常見(jiàn)的具有對(duì)數(shù)時(shí)間的算法有二叉樹(shù)的相關(guān)操作和二分搜索。

對(duì)數(shù)時(shí)間的算法是非常有效的，因?yàn)槊吭黾右粋€(gè)輸入，其所需要的額外計(jì)算時(shí)間會(huì)變小。
遞歸地將字符串砍半并且輸出是這個(gè)類(lèi)別函數(shù)的一個(gè)簡(jiǎn)單例子。它需要O（log n）的時(shí)間因?yàn)槊看屋敵鲋拔覀兌紝⒆址嘲搿?這意味著，如果我們想增加輸出的次數(shù)，我們需要將字符串長(zhǎng)度加倍。

線性時(shí)間

如果一個(gè)算法的時(shí)間復(fù)雜度為O(n)，則稱(chēng)這個(gè)算法具有線性時(shí)間，或O(n)時(shí)間。非正式地說(shuō)，這意味著對(duì)于足夠大的輸入，運(yùn)行時(shí)間增加的大小與輸入成線性關(guān)系。例如，一個(gè)計(jì)算列表所有元素的和的程序，需要的時(shí)間與列表的長(zhǎng)度成正比。