知识卡片

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

有序数据新增只需局部插入

理解等级:中级

已有数据有序时,新增一个元素可先找其正确位置,再移动/重接需要调整的部分,而不必重新对所有元素完整排序。插入排序的有序前缀思想因此也可用于增量维护。

书中按姓名排列的住客名单只需将新姓名放入合适位置。数组可能仍需O(n)比较/移动,链表可在定位后局部接链;“不用全重排”不等于新增必为O(1),更不代表所有动态数据集都应选择插入排序。

225小型UI有序列表新增可一次定位/移动,不需完整重排;O(n)是一次新增而非把n个原无序项逐个排完。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      增量排序中非常高效。这种情况可能会发生,例如:在某酒店预订系统中。假设系统按姓名列出了所有顾客的名单,同时当有新顾客入住时系统会实时更新。在这种情况下使用插入排序,系统只需要扫视一遍数据,并将新顾客姓名插入列表中,就完成重新排序。

    • · 查看原书依据

      用户一个一个插入进去。这种情况下应该选择哪种排序算法? 答:插入排序。对一个有序队列使用插入排序的时间复杂度为O(n)。 问:假设在生物研究中,我们用1000万个80个字符宽的字符串来表示DNA的信息。这种情况下应该选择哪种排序算法? 答:基数排序。基数排序的性能表现取决于基值的选择和空间的限制。然

    参考来源

    - 位置:《算法精解:C语言描述》第12章《插入排序的描述》(spine1337;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1303_split_001.html;u205-ch12-004)。 - 结论依据:205插入排序定义、增量特性和酒店姓名例全文实读,保留增量与复杂度边界;作废支票只是手动排序比喻,不是资金交易案例。 - 原始内容:增量排序中非常高效。这种情况可能会发生,例如:在某酒店预订系统中。假设系统按姓名列出了所有顾客的名单,同时当有新顾客入住时系统会实时更新。在这种情况下使用插入排序,系统只需要扫视一遍数据,并将新顾客姓名插入列表中,就完成重新排序。 - 位置:《算法精解:C语言描述》第12章《问与答》(spine1357;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1323.html;u225-ch12-004)。 - 结论依据:225小型UI有序列表新增可一次定位/移动,不需完整重排;O(n)是一次新增而非把n个原无序项逐个排完。 - 原始内容:用户一个一个插入进去。这种情况下应该选择哪种排序算法? 答:插入排序。对一个有序队列使用插入排序的时间复杂度为O(n)。 问:假设在生物研究中,我们用1000万个80个字符宽的字符串来表示DNA的信息。这种情况下应该选择哪种排序算法? 答:基数排序。基数排序的性能表现取决于基值的选择和空间的限制。然