知识卡片
就地排序也要说明辅助空间
就地通常指不用随元素数线性增长的独立结果数组,而不是任何一字节额外空间都没有。比较算法时应说明是否计入一个元素的临时缓冲、递归调用栈、元素宽度和其他辅助对象。
本书issort实际malloc一个esize字节的key;qksort的partition分配两个元素缓冲,qksort还递归处理左区间、循环处理右区间,因此仍有调用栈开销。不能只因都在原data数组上修改就宣称辅助空间绝对为零。
空间也不是“归并一定等于快排两倍”这类固定比例:需结合具体实现和输入造成的栈深。此卡说明比较维度,不为尚未读完的归并实现预报准确字节数。
207/02951实际malloc(esize)保存key,结束free;无需另一份n项数组,但不是零辅助字节。每次memcpy成本也与esize有关,不论元素多宽都视常数只是一种模型。
210⁄02955 partition分配pval与temp各esize字节并在成功路径释放,qksort左递归而右侧循环推进。局部交换原地不消除调用栈;若分区不缩小或左侧持续很大,栈成本/终止条件更不可忽略。
212“两倍空间”若指输入加同规模临时结果可作粗略总量说明,不是所有归并实现的必然固定比例;链表重链接或不同合并策略有不同辅助空间。214实际缓冲生命周期另核对,不与快排固定两倍比较。
214/02964当前合并分配esize*(k−i+1)字节。无额外n项数组就不能按这版原样合并,但不能据此说所有归并都绝不可原地实现。递归条件实际if(i),原文“i将小于k因此终止”应为i不再小于k时停止。
217存储包含原data、n项temp及k项counts;辅助空间为O(n+k),总计约2n+k项int而非两个n数组都额外分配。源码先malloc counts再malloc temp,第二次失败直接return-1漏free counts;分配成功后正确末尾释放两者。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 就地排序也要说明辅助空间
- · 插入排序的实现与分析
- · 快速排序的实现与分析
- · 归并排序的描述
- · 归并排序的实现与分析
- · 计数排序的实现与分析
原书出处 · 6 处
- · 查看原书依据
就地排序),而有一些则需要额外的空间来处理和输出数据(虽然可能最终结果还是会拷贝到原始的内存空间中)。 搜索就是在一个数据集中找到一个元素的位置,它可用于任何任务中。一种最简单的、不需要费任何脑筋的搜索方法是:简单地从数据集的一端查找到另一端。这就是所谓的线性搜索。通常,线性搜索用在那些对随机访问支
- · 查看原书依据
不需要额外的空间,因此它只使用无序数据本身的存储空间即可。 示例12-1:插入排序的实现
- · 查看原书依据
递归分割,直到所有的分区都只包含单个元素。在以下介绍的实现方法中,data包含size个无序元素,并存放在单块连续的存储空间中。快速排序不需要额外的存储空间,所以所有分割过程都在data中完成。当qksort返回时,data就是一个有序数据集了。 正如我们看到的,快速排序的关键部分是如何分割数据。这
- · 查看原书依据
额外的存储空间来完成排序过程。 我们再回顾那个对一堆作废的支票进行排序的例子。首先,将这堆未排序的废旧支票对半分为两堆。接着,分别又将两堆支票对半分为两堆,以此类推,重复此过程,直到每一堆支票只包含一张支票。一旦所有的堆都只包含一张支票,就开始将堆两两合并,这样每个合并出来的堆就是两个有序堆的合集,
- · 查看原书依据
分配足够的内存。在mgsort返回时,最终通过合并得到的有序数据集将会拷贝回data。 正如我们看到的,归并排序最关键的部分是如何将两个有序集合并成一个有序集。这部分工作由函数merge完成(见示例12-5)。它将data中i到j之间的数据集与j+1到k之间的数据集合并成一个i到k的有序数据集。 最
- · 查看原书依据
两个大小为n的数组,一个大小为k的数组。 示例12-6:计数排序的实现