[课业] 102关务-资料结构 第四题

楼主: onlyu0402 (我在故我唱)   2016-08-16 15:26:58
(如果觉得问题太没程度,私希望各位大大鞭小力点)
题目如下:
四、考虑排序(sort)的问题:(每小题10分,共30分)
(一)如果要排序的资料很少,例如只有十几笔资料,那么你将采用快速排序法(quick
sort)?合并排序法(merge sort)?还是气泡排序法(bubble sort)?为什么?
(二)如果要排序的资料很多,例如多到超过主内存容量许多,那么你将采用快速排序
法?合并排序法?还是气泡排序法?为什么?
小弟拟答如下:
(一)(1)气泡排序法。(2)虽然快速排序法与合并排序法所需的平均时间复杂度为O(nlogn)
皆优于气泡排序法的O(n^2),但因需要处理的资料量不大,故所实际花费时间相差不大且
气泡排序法实作较简单易懂。
(二)(1)气泡排序法。(2)因为快速排序法与合并排序法皆采用divide and conquer的解法
,以递回的方式实作,将消耗大量内存空间,故若资料量过大内存可能不敷使用。
以上拟答中,对于第(二)题较没把握,因为资料量大气泡排序真的会跑很久,但题目
又提到资料多到超过内存容量许多...所以恳求各位先进指点一下观念Orz
作者: lexus7310 (Fox)   2016-08-16 19:35:00
第一题写的不够仔细 第二题是合并排序合并排序的目的就是用于内存不足所以需要大量的资料搬移动作

Links booklink

Contact Us: admin [ a t ] ucptt.com