常用的排序算法的時間復雜度和空間復雜度
排序法
最差時間分析 平均時間復雜度 穩(wěn)定度 空間復雜度
冒泡排序 O(n2) O(n2) 穩(wěn)定 O(1)
快速排序 O(n2) O(n*log2n) 不穩(wěn)定 O(log2n)~O(n)
選擇排序 O(n2) O(n2) 穩(wěn)定 O(1)
二叉樹排序 O(n2) O(n*log2n) 不一頂 O(n)
插入排序
O(n2) O(n2) 穩(wěn)定 O(1)
堆排序 O(n*log2n) O(n*log2n) 不穩(wěn)定 O(1)
希爾排序 O O 不穩(wěn)定 O(1)
1冈闭、時間復雜度
（1）時間頻度 一個算法執(zhí)行所耗費的時間俱尼，從理論上是不能算出來的，必須上機運行測試才能知道萎攒。但我們不可能也沒有必要對每個算法都上機測試遇八，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了耍休。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例刃永，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多羊精。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度斯够。記為T(n)。
（2）時間復雜度 在剛才提到的時間頻度中喧锦，n稱為問題的規(guī)模读规，當n不斷變化時，時間頻度T(n)也會不斷變化燃少。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律束亏。為此，我們引入時間復雜度概念供汛。 一般情況下枪汪，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)涌穆，用T(n)表示，若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時雀久，T（n)/f(n)的極限值為不等于零的常數(shù)宿稀，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進時間復雜度赖捌，簡稱時間復雜度祝沸。
在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個常數(shù)越庇，則時間復雜度為O(1),另外罩锐，在時間頻度不相同時，時間復雜度有可能相同卤唉，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同涩惑，但時間復雜度相同，都為O(n2)桑驱。 按數(shù)量級遞增排列竭恬，常見的時間復雜度有：常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),...熬的， k次方階O(nk),指數(shù)階O(2n)痊硕。隨著問題規(guī)模n的不斷增大，上述時間復雜度不斷增大押框，算法的執(zhí)行效率越低岔绸。 2、空間復雜度 與時間復雜度類似橡伞，空間復雜度是指算法在計算機內執(zhí)行時所需存儲空間的度量盒揉。記作: S(n)=O(f(n)) 我們一般所討論的是除正常占用內存開銷外的輔助存儲單元規(guī)模。討論方法與時間復雜度類似骑歹，不再贅述预烙。
（3）漸進時間復雜度評價算法時間性能 主要用算法時間復雜度的數(shù)量級(即算法的漸近時間復雜度)評價一個算法的時間性能。
2道媚、類似于時間復雜度的討論扁掸，一個算法的空間復雜度(Space Complexity)S(n)定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)最域。漸近空間復雜度也常常簡稱為空間復雜度谴分。
空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機存儲器上所占用的存儲空間镀脂，包括存儲算法本身所占用的存儲空間牺蹄，算法的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面。算法的輸入輸出數(shù)據(jù)所占用的存儲空間是由要解決的問題決定的薄翅，是通過參數(shù)表由調用函數(shù)傳遞而來的沙兰，它不隨本算法的不同而改變氓奈。存儲算法本身所占用的存儲空間與算法書寫的長短成正比，要壓縮這方面的存儲空間鼎天，就必須編寫出較短的算法舀奶。算法在運行過程中臨時占用的存儲空間隨算法的不同而異，有的算法只需要占用少量的臨時工作單元斋射，而且不隨問題規(guī)模的大小而改變育勺，我們稱這種算法是“就地/"進行的，是節(jié)省存儲的算法罗岖，如這一節(jié)介紹過的幾個算法都是如此涧至；有的算法需要占用的臨時工作單元數(shù)與解決問題的規(guī)模n有關，它隨著n的增大而增大桑包，當n較大時南蓬，將占用較多的存儲單元，例如將在第九章介紹的快速排序和歸并排序算法就屬于這種情況捡多。
如當一個算法的空間復雜度為一個常量蓖康，即不隨被處理數(shù)據(jù)量n的大小而改變時，可表示為O(1)垒手；當一個算法的空間復雜度與以2為底的n的對數(shù)成正比時，可表示為0(10g2n)倒信；當一個算法的空I司復雜度與n成線性比例關系時科贬，可表示為0(n).若形參為數(shù)組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間鳖悠，即一個機器字長空間榜掌；若形參為引用方式，則也只需要為其分配存儲一個地址的空間乘综，用它來存儲對應實參變量的地址憎账，以便由系統(tǒng)自動引用實參變量。
