当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 7 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : 求教:从一道算法作业引出的问题
帖子发表于 : 2007-05-26 18:19 
头像

注册: 2007-02-21 23:56
帖子: 224
地址: 广州
送出感谢: 0 次
接收感谢: 0 次
有一道算法作业,用 归并排序 和 快速排序
对 20 个数组, 每个数组有 5000 个元素 进行排序
比较两种算法耗时~
结果在 windows xp 下与 ubuntu 下的结果刚好相反
我还没有学习过 操作系统原理 之类的知识
请各位告知其中的相关原理


页首
 用户资料  
 
2 楼 
 文章标题 :
帖子发表于 : 2007-05-26 20:47 
头像

注册: 2006-05-03 0:39
帖子: 8273
地址: المريخ
送出感谢: 0 次
接收感谢: 1
你把具体程序、计时方法、具体编译方法、机器环境等等给贴出来。

机器环境:估计你的机器太快了,主要时间并不在排序上。

你可以尝试:5000*200,进而50000*200。


_________________
PHP是最好的语言!不服来战!


页首
 用户资料  
 
3 楼 
 文章标题 :
帖子发表于 : 2007-05-26 20:50 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
stlxv 写道:
你把具体程序、计时方法、具体编译方法、机器环境等等给贴出来。

机器环境:估计你的机器太快了,主要时间并不在排序上。

你可以尝试:5000*200,进而50000*200。


一样的观点 , 如果数据足够多且足够随机快排肯定是比归并排快的
两者都是 O(nlogn) , 但快排的因子小一些


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
4 楼 
 文章标题 :
帖子发表于 : 2007-05-26 21:10 
头像

注册: 2007-02-21 23:56
帖子: 224
地址: 广州
送出感谢: 0 次
接收感谢: 0 次
代码见附件


附件:
文件注释: 排序代码
sort.rar [1.35 KiB]
被下载 19 次
页首
 用户资料  
 
5 楼 
 文章标题 :
帖子发表于 : 2007-05-26 21:52 

注册: 2006-09-07 22:51
帖子: 849
送出感谢: 0 次
接收感谢: 0 次
可以把你的代码拿到unix-center的机器上试试啊!!
快速排序:
我的32位 256 ram 比 它 64位 2core 1Gram 还快
排序时间持续 26-29 妙(太长 我不想等)

那台服务器 右8个用户登录
ps aux|wc -l
80
我的
ps aux|wc -l
90
这都是sort 后的结果
我的算法完全是"数据结构" 里
几乎抄来的


页首
 用户资料  
 
6 楼 
 文章标题 :
帖子发表于 : 2007-05-27 10:11 

注册: 2007-01-03 0:19
帖子: 11
送出感谢: 0 次
接收感谢: 0 次
5000个元素什么都不能说明

验证一个排序算法的效率最起码要用百万级别的元素

还有就算是C语言里面自带的快排 据实验sort要比sqort快

所以比较之前应该把各自排序的算法贴出来


页首
 用户资料  
 
7 楼 
 文章标题 :
帖子发表于 : 2007-05-27 20:14 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
快排关键在于快速划分算法


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 7 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 4 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译