排序算法比較
| 排序算法 | 平均時(shí)間 | 最差情形 | 穩(wěn)定度 | 額外空間 | 備注 |
|---|---|---|---|---|---|
| 冒泡 | O(n2) | O(n2) | 穩(wěn)定 | O(1) | n小的時(shí)候較好 |
| 交換 | O(n2) | O(n2) | 不穩(wěn)定 | O(1) | n小的時(shí)候較好 |
| 選擇 | O(n2) | O(n2) | 不穩(wěn)定 | O(1) | n小的時(shí)候較好 |
| 插入 | O(n2) | O(n2) | 穩(wěn)定 | O(1) | 大部分已排序時(shí)較好 |
| 基數(shù) | O( |
O( |
穩(wěn)定 | O(1) | R是基數(shù)，B是真數(shù) |
| shell | O( |
O(ns) 1<s<2 | 不穩(wěn)定 | O(1) | s是所選分組 |
| 快速 | O( |
O(n2) | 不穩(wěn)定 | O( |
n大時(shí)較好 |
| 歸并 | O( |
O( |
穩(wěn)定 | O(1) | n大時(shí)較好 |
| 堆 | O( |
O( |
不穩(wěn)定 | O(1) | n大時(shí)較好 |
其他
| 算法 | 平均時(shí)間 |
|---|---|
| 哈希 | O(1) |
| 二分查找 | O( |
| 二叉搜索樹 | O( |
| 線性商源，遍歷 | O(n) |
算法時(shí)間復(fù)雜度數(shù)排序依次：
常數(shù)階O(1) < 對(duì)數(shù)階O()
< 線性階O(n) < 線性對(duì)數(shù)階O(n*)
< 平方階O(n2) < 立方階O(n3) < k次方階O(nk) < 指數(shù)階O(2n).......
