排序链接列表时,优先使用“合并”排序而不是“快速”排序?

作者 : IT 大叔 本文共340个字,预计阅读时间需要1分钟 发布时间: 2020-10-13

回答:

  • 快速排序取决于能否索引(或随机访问)到数组或类似结构中。如果可能的话,很难击败Quicksort。
  • 您不能很快地直接索引到链接列表。也就是说,如果myList是链表,则myList[x]如果可能编写这样的语法,则将涉及从链表的开头开始并跟随第一个x链接。对于Quicksort进行的每个比较,都必须做两次,这将使真正的快速变得昂贵。
  • 磁盘上的内容相同-Quicksort必须查找并阅读要比较的每个项目。
  • 在这种情况下,合并排序会更快,因为它会顺序读取项目,通常log(n)会遍历数据。所涉及的I / O更少,并且在链接列表中的链接后面花费的时间也更少。
  • 当数据适合内存时,Quicksort速度很快,并且可以直接寻址。当数据无法容纳到内存中或需要昂贵的物品时,Mergesort会更快。
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 排序链接列表时,优先使用“合并”排序而不是“快速”排序?

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论