阅读 330

学习算法第二天

桶排序升级

第一天的桶排序,其实有很多的局限性,传进来的数组中,只能是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之间的数,那么我们之需要重复使用两次桶就可以了。

就上述情况,我们就还可以避免不必要的空间和时间的浪费。

关注下面的标签,发现更多相似文章
评论