|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- 数据结构教材一道课后题的疑问 (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=36744) |
|
-- 作者：chyl -- 发布时间：8/13/2006 11:24:00 PM -- 数据结构教材一道课后题的疑问 7.23题： 教材中那些算法不不要访问已排好序的纪录。 有没有快速排序呢？给的答案是没有，但觉得的确是不用再访问了啊。。。。  7.24题： 7.25题（3） |
|
-- 作者：Supremgoooo -- 发布时间：8/20/2006 3:16:00 PM -- 我同意1，3，不同意2 1。快速排序一趟下来只有轴被排好，在下一轮中它是不被访问的。教材中答案可能是考虑到了改进的快速排序，因为直接插入排序是需要访问排好的记录的。 2。如果用一个指针pointer保存这个位置，每当选择到一个第i小的就与之交换，然后另pointer=pointer->next行不行呢？ 3。答案好像错了。5个记录哪有用归并的？应该按你说的，用改进的插入排序。 |
|
-- 作者：chyl -- 发布时间：8/21/2006 3:45:00 PM -- 1。改进的似乎也不用访问排好的的纪录吧？我不很确定，你能举个例子吗？ 2。你的意思我没看懂，为什么要换2分查找呢？不是直接选择排序吗？ |
|
-- 作者：Supremgoooo -- 发布时间：8/21/2006 5:12:00 PM -- 1。例如：待排数组中的元素依次为[1，3，2]，则由于该数组长度小于门槛，算法进入直接插入排序。在第一轮后，数组为[1，3，2]，其中1，3已经排好，第二轮过后，数组为[1，2，3]，可见排好的元素2被换到了3的位置。 2。直接选择每次都在剩下的元素中选最小值。这就注定该算法是可以借助某个优先队列加以提高效率。例如选堆，它是一种逻辑上的二叉树，其逻辑结构的查找过程为2分查找，如果用链表实现，则各节点之间的逻辑关系需要指针反复移动实现，而这样的移动开销太大，得不偿失。 |
|
-- 作者：chyl -- 发布时间：8/21/2006 11:25:00 PM -- 1.似乎在第一轮后，数组就已经排好序了。所以应该是不用再访问的啊，而且如果改进的口快速排序还要访问已经排好的轴值，就说明它还需要再改进，我想我可以写出这个程序来。 2.直接选择排序的确可以借助某些方法提高效率，但是实际上并没有借助啊。 |
|
-- 作者：Supremgoooo -- 发布时间：8/22/2006 9:34:00 PM -- 1.咋会一轮？在我给的例子下，它和轴值咋会有关？此时算法已经完全变成了直接插入排序。 2.实际上借助的还要复杂哩，例如F堆等等。总之，选择算法在每找一个值时，指针的移动量太大。在张铭的课件中写到：当读操作比插入删除操作频率大时，不应选择链表。 |
|
-- 作者：chyl -- 发布时间：8/23/2006 12:59:00 PM -- 1。我明白你的意思了：） 2。你的意思是说，指针从头到尾移动一遍的话，量很大吗？为什么呢？ |
|
-- 作者：Supremgoooo -- 发布时间：8/23/2006 7:42:00 PM -- 2.这里面是一个利弊权衡的问题，从硬着头皮做的角度上，这些算法都可以用链表实现。但是算法本身是讲究效率的。为了找一个数就遍历整个数组可能已经是最坏的算法了。 关于链表与数组的区别，可以看下这张幻灯片： |
|
-- 作者：chyl -- 发布时间：8/25/2006 7:36:00 PM -- 好的，谢谢！ |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
125.000ms |
此主题相关图片如下：