dafa888黄金版登录

首页 > 正文

学习算法第二天

www.tadcxc.com2019-07-19

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

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

  

  排序.png

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

  高位数中数字大的,无论它低位数多小,它依旧大。(所以我们要从低位开始进行排序)

  从数字大的桶中先往出倒数据,那么大的数据一定是排在前面的。

  上面的基础上,遇到相同数字进行压栈,那么大数字的一定先出来。

  桶排序的数据要求是,所有数据的长度必须完全一样,且已知。所以使用多少次,是常数项。

  桶排序属于稳定排序。

  比如[22(1),22(2)],进行排序之后,肯定是[22(1),22(2)]的顺序。

  这种桶排序的空间复杂度是O(1),10个桶

  这种桶排序的时间复杂度O(n),将所有的数组遍历一遍

  用桶排序,个位开始。

  数字是几,几号桶接。

  同等大小,顺序压栈。

  大桶先倒,一定最大。

  顺位后起,继续接桶。

  最高位完,完成排序。

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

  如果我们的数据中,只有100和101,那么我们准备2个桶就可以完成排序,并不需要10个桶

  如果我们的数据是100~200之间的数,那么我们之需要重复使用两次桶就可以了。

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

热门浏览
热门排行榜
热门标签
日期归档