Algorithm

Author: swanky(swanky.hsiao@gmail.com)
Last Updated: 2004-09-28

注意:某些字元在IE上無法正常顯示,請務必使用 Mozilla 系列瀏覽。若有任何錯誤,請 mail 通知我

比較表 Time Complexity Space Complexity Stable/Unstable
Best Case Worst Case Average Case
Insertion Sort
O(n)
O(n2)
O(n2)
O(1)
Stable
Selection Sort
O(n2)
O(n2)
O(n2)
O(1)
Unstable
Bubble Sort
O(n)
O(n2)
O(n2)
O(1)
Stable
Shell Sort
O(n3/2)
O(n2)
O(n2)
O(1)
Unstable
Quick Sort
O(nlogn)
O(n2)
O(nlogn)
O(logn)~O(n)
Unstable
Merge Sort
O(nlogn)
O(nlogn)
O(nlogn)
O(n)
Stable
Heap Sort
O(nlogn)
O(nlogn)
O(nlogn)
O(1)
Unstable
LSD Radix Sort
O(d*(n+r))
O(n*r)
Stable