几种排序算法的比较
Θ，既是上界也是下界(tight)，等于的意思。
Ο，表示上界(tightness unknown)，小于等于的意思。
ο，表示上界(not tight)，小于的意思。
Ω，表示下界(tightness unknown)，大于等于的意思。
ω，表示下界(not tight)，大于的意思。
O符号是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。
Ω符号的定义与O符号的定义类似，但主要区别是，O符号表示函数在增长到一定程度时总小于一个特定函数的常数倍，大Ω符号则表示总大于，来描述一个函数数量级的渐近下界。
Θ符号是O符号和Ω符号的结合。下面给出具体的数学定义:
函数\(f ( n )\)代表某一算法在输入大小为n的情况下的工作量（效率），则在n趋向很大的时候，我们将f (n)与另一行为已知的函数g(n)进行比较：
1）如果\(lim f(n)/g(n)=0\)，则称f(n)在数量级上严格小于g(n)，记为\(f (n)=o( g(n))\)。
2）如果\(lim f(n)/g(n)=\infty\)，则称f(n)在数量级上严格大于g(n)，记为\(f (n)=ω( g(n))\)。
3）如果\(lim f(n)/g(n)=c\)，这里c为非0常数，则称f(n)在数量级上等于g(n)，即f(n)和g(n)是同一个数量级的函数，记为：\(f(n)=Θ(g(n))\)。
4）如果f(n)在数量级上小于或等于g(n)，则记为\(f(n)=O(g(n))\)。
5）如果f(n)在数量级上大于或等于g(n)，则记为\(f(n)=Ω(g(n))\)。
| 排序方式 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定 | 备注 |
|---|---|---|---|---|---|---|
| 快速 | O(nlogn) | O(\(n^2\)) | O(nlogn) | O(logn) | 不稳定 | 最坏比较次数 $ 2 $ |
| 归并 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | |
| 堆 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | |
| 冒泡 | O(\(n^2\)) | O(\(n^2\)) | O(n) | O(1) | 稳定 | 最坏比较次数 $ 2 $ |
| 选择 | O(\(n^2\)) | O(\(n^2\)) | O(\(n^2\)) | O(1) | 不稳定 | |
| 插入 | O(\(n^2\)) | O(\(n^2\)) | O(n) | O(1) | 稳定 | 最坏比较次数 $ 2 $ |
| 希尔 | O(\(n^2\)) | O(n) | O(1) | 不稳定 | ||
| 基数 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 稳定 | d为位数，r为基数 |
| 计数 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 | k是整数的范围 |
