一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2701|回复: 82
收起左侧

Berkeley CS 61B Homework8

  [复制链接] |试试Instant~ |关注本帖
逃亡~ 发表于 2014-10-5 13:35:59 | 显示全部楼层 |阅读模式

[其他]CS 61B Data Structures(in Java) #1 - 2014-10-04@UC Berkeley

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 逃亡~ 于 2014-10-5 13:37 编辑

homework 8 是对一个queue(实质是一个单向链表)完成mergesort和quicksort,然后分别对比 对100、1000、10000、100000、1000000的size的queue进行mergesort和quicksort的时间。
这个作业挺简单的。
刚开始贴不了图+_+ 后来可以了。。。
更多图片 小图 大图
组图打开中,请稍候......

评分

2

查看全部评分

hypsm 发表于 2016-2-1 23:35:09 | 显示全部楼层
本帖最后由 hypsm 于 2016-2-1 23:36 编辑

5.pic_hd.jpg

在我的算法中,归并排序的merge函数在q1 q2 元素相等时每次优先将q1的元素放入新队列中,因此顺序可能会改变,所以不是stable;
快速排序中,由于有了qEquals队列的存在,相等的元素顺序并不会改变,因此是stable的。


评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

enirinth 发表于 2015-6-10 01:13:54 | 显示全部楼层
先贴作业:

111111.png


MD先把nth()用到partition里面去了。。。。导致q_sort的时间一直不对。。。

关于stable:
merge sort不stable; 因为merge 2 sorted list的时候一边取一个front;这两个sub list有可能先后错位;
quick sort stable; 因为每次相同的key都按顺序放在中间。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| 逃亡~ 发表于 2014-10-5 13:36:18 | 显示全部楼层
本帖最后由 逃亡~ 于 2014-10-5 13:38 编辑

还是quicksort稍微好点啊,尤其是size特别大的时候。
回复 支持 反对

使用道具 举报

南若冲 发表于 2014-10-6 17:06:21 | 显示全部楼层
哈哈这个作业我也做过。这两个平均复杂度都是O(nlogn),不过最坏情况Q-sort是O(n^2), M-sort慢啊。我记得Q-Sort,M-sort, BST, H-sort平均时间复杂度都一样。
回复 支持 反对

使用道具 举报

wtttt0 发表于 2014-11-14 11:35:40 | 显示全部楼层
好像比楼主慢了不少...
1.png
2.png
3.png
4.png
5.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

wtttt0 发表于 2014-11-14 11:35:51 | 显示全部楼层
好像比楼主慢了不少...





回复 支持 反对

使用道具 举报

 楼主| 逃亡~ 发表于 2014-11-15 07:19:01 | 显示全部楼层
wtttt0 发表于 2014-11-14 11:35
好像比楼主慢了不少...

i7-4700MQ
回复 支持 反对

使用道具 举报

voiding 发表于 2014-11-24 12:28:21 | 显示全部楼层
HW8比较简单,完成了,求加学分。
hw8.jpg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

831128 发表于 2014-11-25 13:18:45 | 显示全部楼层
交作业,还有2个作业,坚持住
回复 支持 反对

使用道具 举报

imposiwind 发表于 2014-11-25 22:29:51 | 显示全部楼层
这次作业比较容易,按照提示说明编写分分钟搞定!
加油!!!!

Sort_test

Sort_test

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

831128 发表于 2014-11-26 05:55:37 | 显示全部楼层
上次没发到,现在重发
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

18258170717 发表于 2014-12-7 22:19:57 | 显示全部楼层
831128 发表于 2014-11-26 05:55
上次没发到,现在重发

0msec怎么回事?
回复 支持 反对

使用道具 举报

18258170717 发表于 2014-12-7 22:20:46 | 显示全部楼层
确实比较简单,MergeSort调了一会儿

H8

H8

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

bruce2045 发表于 2015-1-6 13:47:52 | 显示全部楼层
这次作业相对简单,还差最后两次作业,fighting!
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

zj45499 发表于 2015-1-19 14:56:02 | 显示全部楼层
你们的速度都跟打了鸡血一样.......我的机器这么差了...

Screen Shot 2015-01-19 at 2.54.26 PM.jpg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

urekuk 发表于 2015-3-10 17:58:55 | 显示全部楼层
该换电脑了……
result.jpg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

ryanli 发表于 2015-3-31 22:58:14 | 显示全部楼层
交作业交作业
更多图片 小图 大图
组图打开中,请稍候......
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 10:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表