排序與時間複雜度
排序與時間複雜度
資料來源:
https://mp.weixin.qq.com/s/PXt3wfAOvvrWleOBsIAgnA
http://notepad.yehyeh.net/Content/Algorithm/Sort/Sort.php
GITHUB: https://github.com/jash-git/Jash-good-idea-20190128-001
| 演算法 | 時間複雜度 | 空間複雜度 | 穩定性 | 類型 | ||
|---|---|---|---|---|---|---|
| Best | Worst | Avg | ||||
| 選擇排序法(Selection Sort) | Ο(n2) | Ο(n2) | Ο(n2) | Ο(1) | 不穩定 | 選擇 |
| 插入排序法(Insertion Sort) | Ο(n) | Ο(n2) | Ο(n2) | Ο(1) | 穩定 | 插入 |
| 氣泡排序法(Bubble Sort) | Ο(n) | Ο(n2) | Ο(n2) | Ο(1) | 穩定 | 交換 |
| 謝爾排序法(Shell Sort) | Ο(n) | Ο(n2)~ Ο(n1.5) | Ο(n5/4) | Ο(n) + Ο(1) | 不穩定 | 插入 |
| 搖晃排序法(Shaker Sort) | Ο(n) | Ο(n2) | Ο(n2) | Ο(1) | 穩定 | 交換 |
| 快速排序法(Quick Sort) | Ο(n log n) | Ο(n2) | Ο(n log n) | Ο(log n)~Ο(n) | 不穩定 | 交換 |
| 合併排序法(Merge Sort) | Ο(n log n) | Ο(n log n) | Ο(n log n) | Ο(n) | 穩定 | 合併 |
| 堆積排序法(Heap Sort) | Ο(n log n) | Ο(n log n) | Ο(n log n) | Ο(n) + Ο(1) | 不穩定 | 選擇 |
| 基數排序(Radix Sort) | Ο(d×(n+r)) | Ο(d×(n+r)) | Ο(d×(n+r)) | Ο(n×r) | 穩定 | 分配 |
3 thoughts on “排序與時間複雜度”
JavaScript：十大排序的算法思路和代码实现
https://mp.weixin.qq.com/s?__biz=MzI3MzgxNDY2MQ==&mid=2247484195&idx=1&sn=67f454e82cf26238951e8ac8316ecd58&chksm=eb1cc6c9dc6b4fdfdf340011a8a2d9c354905150e53d590a72eac12279b8b604d3551f218705&scene=0&xtrack=1&key=b99eafd7f107cbc37cc00b1b9346c071c3862e80bbef5a94eac7cee210a303e55b62011d3e35e87eabe65025f11ad13cd373f7f3038cfd4d5b31884342ce9cadc50070c2f1c3be2795f5cead42201b47&ascene=1&uin=MjIwODk2NDgxNw%3D%3D&devicetype=Windows+10&version=62060833&lang=zh_TW&pass_ticket=N%2B3SAvoswuWEaoIjwv2dAvKu0ehSZDCneHMAtaNC1aRoCmXoj3CNjhyjeyT2CZ%2Bq
個人認為目前最為推薦 [效率(速度)&額外記憶體使用量&穩定度] 的排序法 – 归并排序/歸併排序/合併排序 (Merge Sort) (2019/06/11 特此紀錄)
排序法的性能評估指標:
穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。
不穩定：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面。
時間複雜度：對排序數據的總的操作次數。反映當n變化時，操作次數呈現什麼規律。
空間複雜度：是指算法在計算機內執行時所需存儲空間的度量，它也是數據規模n的函數。