排序與時間複雜度

排序與時間複雜度

排序與時間複雜度


資料來源:
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) 穩定 分配

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *