Bucket Sort and Cardinality sort
桶排序算法介绍...
桶排序
T(N,M) = O(M+N),M 个桶的情况- N >> M的时候是相对教优秀的算法
- M >> N ???
- 假设我们有N = 10个整数，N ∈ [0,999],(此时 M = 1000)；我们便不能在线性时间下完成排序。
基数排序：按照数字的进制排序（10）
- example:
- input: 64 8 216 512 27 729 0 1 343 125
- 使用次位优先(Least Significant Digit)
- 先按照个位数将元素放到对应的桶Pass1
- 按照十位放到对应的桶中
| Bucket | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Pass 1(个位) | 0 | 1 | 512 | 343 | 64 | 125 | 216 | 27 | 8 | 729 |
| Pass 2(十位) | 0 1 8 |
512 216 |
125 27 729 |
343 | 64 |
|||||
| Pass 3 (百位) | 0 1 8 27 64 |
125 | 216 | 343 | 512 | 729 |
- 最终的顺序，分别从每个桶中顺序读取即可。
时间复杂度： T= O(P(N+B))
- 较好情况：取决于基数-多少个桶 (B << N时差不多是一个线性复杂度的算法)