排序與時間複雜度

排序與時間複雜度

排序與時間複雜度


資料來源:
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 “排序與時間複雜度

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

  2. 排序法的性能評估指標:

    穩定:如果a原本在b前面,而a=b,排序之後a仍然在b的前面。

    不穩定:如果a原本在b的前面,而a=b,排序之後a可能會出現在b的後面。

    時間複雜度:對排序數據的總的操作次數。反映當n變化時,操作次數呈現什麼規律。

    空間複雜度:是指算法在計算機內執行時所需存儲空間的度量,它也是數據規模n的函數。

發表迴響

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