黑马程序员技术交流社区
标题: 最快最简单的排序算法：桶排序 [打印本页]
作者: Wanibal 时间: 2016-5-3 17:49
标题: 最快最简单的排序算法：桶排序
最近看了一篇文章，讲的是桶排序的算法，不过文章主人是用C++实现的，于是就想能不能用java实现一下，下面是部分原文内容和我的java代码，写的比较简单，有什么意见和想法欢迎大家提出来交流交流。
先举个栗子介绍一下桶排序的思想
期末考试完了老师要将同学们的分数按照从高到低排序。小明的班上只有5个同学，这5个同学分别考了5分、3分、5分、2分和8分，哎考的真是惨不忍睹（满分是10分）。接下来将分数进行从大到小排序，排序后是8 5 5 3 2。你有没有什么好方法编写一段程序，让计算机随机读入5个数然后将这5个数从大到小输出？请先想一想，至少想15分钟再往下看吧(*^__^*) 。
我们这里只需借助一个一维数组就可以解决这个问题。请确定你真的仔细想过再往下看哦。
首先我们需要申请一个大小为11的数组int a[11]。OK现在你已经有了11个变量，编号从a[0]~a[10]。刚开始的时候，我们将a[0]~a[10]都初始化为0，表示这些分数还都没有人得过。例如a[0]等于0就表示目前还没有人得过0分，同理a[1]等于0就表示目前还没有人得过1分……a[10]等于0就表示目前还没有人得过10分。
下面开始处理每一个人的分数，第一个人的分数是5分，我们就将相对应a[5]的值在原来的基础增加1，即将a[5]的值从0改为1，表示5分出现过了一次。
第二个人的分数是3分，我们就把相对应a[3]的值在原来的基础上增加1，即将a[3]的值从0改为1，表示3分出现过了一次。
注意啦！第三个人的分数也是“5分”，所以a[5]的值需要在此基础上再增加1，即将a[5]的值从1改为2。表示5分出现过了两次。
按照刚才的方法处理第四个和第五个人的分数。最终结果就是下面这个图啦。
你发现没有，a[0]~a[10]中的数值其实就是0分到10分每个分数出现的次数。接下来，我们只需要将出现过的分数打印出来就可以了，出现几次就打印几次，具体如下：
[backcolor=rgb(238, 238, 238) !important]
最终屏幕输出“2 3 5 5 8”，完整的代码如下。
作者: 非洲小孩 时间: 2016-5-3 18:16
冒泡排序
作者: Huangzikun 时间: 2016-5-3 18:20
妥妥的冒泡排序
作者: Wanibal 时间: 2016-5-3 20:11
本帖最后由 Wanibal 于 2016-5-3 20:24 编辑
桶排序的时间复杂度为O(m+n)。m为桶的个数，n为待排序数的个数冒泡排序的时间复杂度是O(n2)
作者: Wanibal 时间: 2016-5-3 20:13
完全不一样的啊
作者: 布德鸟 时间: 2016-5-3 20:25
方法不错，不知道在随机值范围较大的情况下，有没有什么弊端
作者: 大大史莱姆 时间: 2016-5-3 20:41
某些地方确实是不错
不过总感觉有点弊端，才刚开始学，也说不上来。
作者: Wanibal 时间: 2016-5-3 20:51
是啊，缺点就是随机值分布范围比较大的话，就非常占用内存空间了
作者: dtmacg 时间: 2016-5-3 21:05
冒泡排序
作者: 沙漠中的狼 时间: 2016-5-3 21:17
设计的挺好的,只不过包我们还没学,嘿嘿,其他都简单,就差一个打包过程
作者: 追忆睡梦已醒 时间: 2016-5-3 21:51
嗯嗯，看起来是是这样的
作者: pal_xie 时间: 2016-5-3 21:58
万一整数比较大呢
作者: lishihao88 时间: 2016-5-3 22:00
感谢分享啊，学习一下。
作者: 你是我的菜 时间: 2016-5-3 22:23
这个不错，支持一下啊
作者: xiao宇 时间: 2016-5-3 22:29
冒泡排序
作者: tongtian 时间: 2016-5-3 22:38
加油加油加油加油加油
作者: 风色月下 时间: 2016-5-3 22:42
学习了{:2_30:}
作者: xiangzhuni886 时间: 2016-5-3 22:43
66666666666666666666666
作者: wushi黑马 时间: 2016-5-3 22:47
我记的使用ｃ实现的不是Ｃ＋＋
作者: sfz6012 时间: 2016-5-3 22:50
完全看不懂, 你不会出现角标越界?
作者: 张立鹏 时间: 2016-5-3 22:55
相比冒泡排序,桶排序是用空间换时间
作者: 心悟 时间: 2016-5-3 22:55
嗯, 居然上首页了
作者: feijiaqi 时间: 2016-5-3 22:58
排序排序 排序
作者: w125621538 时间: 2016-5-3 23:02
貌似很6的样子
作者: sfz6012 时间: 2016-5-3 23:04
看了你的文字说明 装个b
你这个只能排整数型 double什么的排不了
你这个得知道愿数组的最大值,不然会角标越界吧(新手,不肯定)
如果最大值很大,接近long的最值,运算时间会不会很长(这个瞎想的)
作者: saiqqww234 时间: 2016-5-3 23:10
学习了。。。。
作者: Wanibal 时间: 2016-5-3 23:17
是啊，这个是最简单的桶排序，真正的桶排序可以排double型的，不过比较复杂；至于你说的后两个问题，也是桶排序的缺陷。
作者: Wanibal 时间: 2016-5-3 23:19
嗯 ，说的很对，不过排一些比较集中的数还是很快的。
作者: Wanibal 时间: 2016-5-3 23:20
整数比较大，就得创建一个很大的数组来装他，所以就比较占空间，这也是它的缺点。
作者: Wanibal 时间: 2016-5-3 23:21
额，因为我也没学过C和C++,只是看起来感觉很像C++，哈哈
作者: Wanibal 时间: 2016-5-3 23:23
你定义的第二个数组，它的空间大于第一个数组的空间同时大于第一个数组中的最大值就可以了；这种排序很有局限性，但是当条件都适合的时候，它确实速度很快。
作者: sjxaa888 时间: 2016-5-3 23:25
冒泡排序
作者: 崔耀恒_b4ApR 时间: 2016-5-4 00:11
真心看了半天
作者: sywy328826 时间: 2016-5-4 00:14
666666666666666666666
作者: z736886202 时间: 2016-5-4 00:23
不错啊
作者: zcstc2003 时间: 2016-5-4 08:48
挺好的东西，这确实降低了时间复杂度，不过能用的场合很少
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |