1. 时间复杂度:O(N + C),C=N*(logN-logM)
对于待排序序列大小为 N,共分为 M 个桶,主要步骤有:
N 次循环,将每个元素装入对应的桶中
M 次循环,对每个桶中的数据进行排序(平均每个桶有 N/M 个元素)
一般使用较为快速的排序算法,时间复杂度为 O(NlogN),实际的桶排序过程是以链表形式插入的。
整个桶排序的时间复杂度为:
O(N)+O(M∗(N/M∗log(N/M))) = O(N)+O(N∗(log(N/M)) = O(N)+O(C)= O(N∗(log(N/M)+1))
当 N = M 时,复杂度为 O(N)
2. 额外空间复杂度:O(N + M)
3、稳定性分析
桶排序的稳定性取决于桶内排序使用的算法。