桶排序思想

桶排序思想

算法思想

大O分析

时间

• 求最大最小值n
• 便利装桶 n
• 桶内排序 n/k * log(n/k) *k
• 输出结果 n
• 3n + k + n/k * log(n/k) k = 3n + k + nlog(n/k) 与等于 n + k
• 最坏n方 （一个桶）
• 最好为n（n个桶而且值排列均匀）

空间

• n + k
• 但实际上空间做到最好的话，就只能用链表，时间就做不到最好