知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.1 · 生成模型:未记录

就地排序也要说明辅助空间

理解等级:中级

就地通常指不用随元素数线性增长的独立结果数组,而不是任何一字节额外空间都没有。比较算法时应说明是否计入一个元素的临时缓冲、递归调用栈、元素宽度和其他辅助对象。

本书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:计数排序的实现

    参考来源

    - 位置:《算法精解:C语言描述》第12章《第12章 排序和搜索》(spine1337;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1303_split_001.html;u204-ch12-002)。 - 结论依据:204就地/额外空间及算法概述全文实读,207完整issort.c与210完整qksort.c实际malloc/递归边界支撑,未执行内存测量。 - 原始内容:就地排序),而有一些则需要额外的空间来处理和输出数据(虽然可能最终结果还是会拷贝到原始的内存空间中)。 搜索就是在一个数据集中找到一个元素的位置,它可用于任何任务中。一种最简单的、不需要费任何脑筋的搜索方法是:简单地从数据集的一端查找到另一端。这就是所谓的线性搜索。通常,线性搜索用在那些对随机访问支 - 位置:《算法精解:C语言描述》第12章《插入排序的实现与分析》(spine1339;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1305.html;u207-ch12-002)。 - 结论依据:207/02951实际malloc(esize)保存key,结束free;无需另一份n项数组,但不是零辅助字节。每次memcpy成本也与esize有关,不论元素多宽都视常数只是一种模型。 - 原始内容:不需要额外的空间,因此它只使用无序数据本身的存储空间即可。 示例12-1:插入排序的实现 - 位置:《算法精解:C语言描述》第12章《快速排序的实现与分析》(spine1342;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1308.html;u210-ch12-002)。 - 结论依据:210/02955 partition分配pval与temp各esize字节并在成功路径释放,qksort左递归而右侧循环推进。局部交换原地不消除调用栈;若分区不缩小或左侧持续很大,栈成本/终止条件更不可忽略。 - 原始内容:递归分割,直到所有的分区都只包含单个元素。在以下介绍的实现方法中,data包含size个无序元素,并存放在单块连续的存储空间中。快速排序不需要额外的存储空间,所以所有分割过程都在data中完成。当qksort返回时,data就是一个有序数据集了。 正如我们看到的,快速排序的关键部分是如何分割数据。这 - 位置:《算法精解:C语言描述》第12章《归并排序的描述》(spine1344;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1310.html;u212-ch12-002)。 - 结论依据:212“两倍空间”若指输入加同规模临时结果可作粗略总量说明,不是所有归并实现的必然固定比例;链表重链接或不同合并策略有不同辅助空间。214实际缓冲生命周期另核对,不与快排固定两倍比较。 - 原始内容:额外的存储空间来完成排序过程。 我们再回顾那个对一堆作废的支票进行排序的例子。首先,将这堆未排序的废旧支票对半分为两堆。接着,分别又将两堆支票对半分为两堆,以此类推,重复此过程,直到每一堆支票只包含一张支票。一旦所有的堆都只包含一张支票,就开始将堆两两合并,这样每个合并出来的堆就是两个有序堆的合集, - 位置:《算法精解:C语言描述》第12章《归并排序的实现与分析》(spine1346;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1312.html;u214-ch12-002)。 - 结论依据:214/02964当前合并分配esize*(k−i+1)字节。无额外n项数组就不能按这版原样合并,但不能据此说所有归并都绝不可原地实现。递归条件实际if(i<k),原文“i将小于k因此终止”应为i不再小于k时停止。 - 原始内容:分配足够的内存。在mgsort返回时,最终通过合并得到的有序数据集将会拷贝回data。 正如我们看到的,归并排序最关键的部分是如何将两个有序集合并成一个有序集。这部分工作由函数merge完成(见示例12-5)。它将data中i到j之间的数据集与j+1到k之间的数据集合并成一个i到k的有序数据集。 最 - 位置:《算法精解:C语言描述》第12章《计数排序的实现与分析》(spine1349;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1315.html;u217-ch12-002)。 - 结论依据:217存储包含原data、n项temp及k项counts;辅助空间为O(n+k),总计约2n+k项int而非两个n数组都额外分配。源码先malloc counts再malloc temp,第二次失败直接return-1漏free counts;分配成功后正确末尾释放两者。 - 原始内容:两个大小为n的数组,一个大小为k的数组。 示例12-6:计数排序的实现