跟我学算法(一)——超快而简单的排序——桶排序

排序充斥着我们的生活,站队、排队买票、考试排名、苦逼的公司业绩排名、email中邮件按时间排序、qq好友列表里红名靠前等等。

下面举个例子介绍下排序算法

举个栗子

 

期末考试,老师要把大家的分数排序,比如有5个学生,分别考5、3、5、2、8分(满分十分),从大到小排序应该是8、5、5、3、2,大家有没有办法能够写段程序随机读入5个数,然后排序呢?

 

这里应该给自己点时间自己想想。就5分钟把,想想再往下看。

提示一下,用个一维数组就可以咯~

 

这里用一个数组,长度为11,刚开始的时候值都初始化为0。

Int [] a = new int[11];

数组

 

下面开始处理,遍历考分,多少分,就在多少下标处的值加1。如第一个5分,就a[5]的值加1。

数组

 

以此类推下面的就直接上图。

数组

 

数组'

最终如下:

数组

 

这里其实a[0]~a[10]就是0-10分,每个里面的值就是得这个分的人数。接下来我们只需要倒序将有分数的值打印出相应的次数就行了。

 

这种排序我们暂且先叫他桶排序,但实际上真正的桶排序要比这个复杂的多,这个我们以后再说。

 

这个算法就好比我们有11个桶,编号从0-10,每出现一个值,就在对应桶里放一个小旗,最后只需要按顺序数下每个桶里的旗子个数就行了。

 

最后就是算法里很重要的一点,时间复杂度,一个是桶子个数M的循环,一个是排序数字个数的循环N,分别都要循环两次,所以时间复杂度是O(2*(M+N)),忽略常熟记为O(M+N)。空间复杂度是O(M+N),当然,如果数值范围非常大,桶的个数特别多,空间的代价肯定也是不切实际的,所以这个算法也是有所局限的。

 

最后,再跟大家分享一个情况,就是如果排序的数字中,每个数字都是唯一的,我们还能更加精简空间,这里就可以不使用int类型而是用boolean类型,就可以了。实际每位占用空间只有1个bit。(算法上来说是这样,或者有的语言有bit类型)

说到这里在给大家分享一个java虚拟机里内存存储的相关知识。

虽然boolean只占1个bit就够了,但是java实际的情况是占用多少不确定,但肯定比1bit多。在咱们的数组的情况下是占1字节。

关于这个的更多内容可以参考http://irfen.me/java-basic-data-type-space

 

©原创文章,转载请注明来源: 赵伊凡's Blog
©本文链接地址: 跟我学算法(一)——超快而简单的排序——桶排序

“跟我学算法(一)——超快而简单的排序——桶排序”的36个回复

  1. Pingback: loans online
  2. Pingback: how to calculate bmi
  3. Pingback: Blue Coaster33
  4. Pingback: best online casinos
  5. Pingback: online casinos
  6. Pingback: get satellite tv
  7. Pingback: parking
  8. Pingback: fue
  9. Pingback: water ionizer machine
  10. Pingback: stop parking
  11. Pingback: paypal loans
  12. Pingback: water ionizer loans
  13. Pingback: electricians 19067
  14. Pingback: plumbers q&a
  15. Pingback: plumbers nevada mo
  16. Pingback: house blue
  17. Pingback: check here
  18. Pingback: check this
  19. Pingback: HD Coloring Pages
  20. Pingback: ionizer payment plan
  21. Pingback: electricity
  22. Pingback: alkaline water
  23. Pingback: alkaline water
  24. Pingback: cheap car insurance
  25. Pingback: water ionizer
  26. Pingback: this post
  27. Pingback: over here

赵伊凡进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注