Monday, May 17, 2004
Sorts比較
比較各Sorts:
時間複雜度
in-place or not in-place
stable or unstable
《Sorts比較》
| 比較表 | 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 |
||
