排序與時間複雜度

排序與時間複雜度

排序與時間複雜度


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

2 thoughts on “排序與時間複雜度

  1. 個人認為目前最為推薦 [效率(速度)&額外記憶體使用量&穩定度] 的排序法 – 归并排序/歸併排序/合併排序 (Merge Sort) (2019/06/11 特此紀錄)

發表迴響

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