桶排序升级

第一天的桶排序，其实有很多的局限性，传进来的数组中，只能是0~9的数字，如果是多位数的情况，就需要升级一下。

先举一个例子：

对数组[123,222,219]进行排序

排序.png

解决思路：

我们将多位数进行拆解，每位数的数字依旧是0~9，那么我们还是需要10个桶，只不过我们的桶可以重复利用，有多少位就用多少次。上面的题，我们的桶就用了3次。其中用到的原理。

原理介绍：

1. 高位数中数字大的，无论它低位数多小，它依旧大。（所以我们要从低位开始进行排序）
2. 从数字大的桶中先往出倒数据，那么大的数据一定是排在前面的。
3. 上面的基础上，遇到相同数字进行压栈，那么大数字的一定先出来。

特点

• 桶排序的数据要求是，所有数据的长度必须完全一样，且已知。所以使用多少次，是常数项。
• 桶排序属于稳定排序。
  比如[22(1),22(2)]，进行排序之后，肯定是[22(1),22(2)]的顺序。
• 这种桶排序的空间复杂度是O(1)，10个桶
• 这种桶排序的时间复杂度O(n)，将所有的数组遍历一遍

口诀：

用桶排序，个位开始。
数字是几，几号桶接。
同等大小，顺序压栈。
大桶先倒，一定最大。
顺位后起，继续接桶。
最高位完，完成排序。

局限

这种排序算法，虽然较之前的有些改进，但是它依旧有一些局限性。

1. 如果我们的数据中，只有100和101，那么我们准备2个桶就可以完成排序，并不需要10个桶
2. 如果我们的数据是100~200之间的数，那么我们之需要重复使用两次桶就可以了。
   就上述情况，我们就还可以避免不必要的空间和时间的浪费。