常用排序法時間複雜整理介紹:
常用排序法時間複雜整理介紹:
本篇是整理常用排序法的時間複雜度的相關資訊，歡迎有需要的(C/P)同好來(C/P)一下。
|
氣泡排序法(Bubble) |
選擇排序法(Selection) |
插入排序法(Insert) |
謝爾排序法(Shell) |
快速排序法 (Quick) |
基數排序法 (Base) |
|
|
時間複雜 |
O(n)/O(n2) |
O(n2) |
O(n2) |
O(n1.5) |
O(nlog2n)/O(n2) |
O(nlogpk) |
|
種類 |
穩定 |
不穩定 |
穩定 |
不穩定 |
不穩定 |
穩定 |
|
備註 |
最慢的排序法 |
適合資料量小或部分資料以排序 |
適合資料量小 |
資料量很大時是最快的算法 |
目前公認最佳的排序法 |
需要很大的額外空間 (k 是資料最大值, p 固定或很小) |
2 thoughts on “常用排序法時間複雜整理介紹:”
個人認為目前最為推薦 [效率(速度)&額外記憶體使用量&穩定度] 的排序法 – 归并排序/歸併排序/合併排序 (Merge Sort) (2019/06/11 特此紀錄)
排序法的性能評估指標:
穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。
不穩定：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面。
時間複雜度：對排序數據的總的操作次數。反映當n變化時，操作次數呈現什麼規律。
空間複雜度：是指算法在計算機內執行時所需存儲空間的度量，它也是數據規模n的函數。