知识卡片

普通读书笔记卡 · 3593

插入排序维护有序前缀

理解等级:初级

插入排序每轮取出当前位置的键,向右移动有序前缀中更大的键,再把它放入空位。

比较条件为“大于”时,相等的键不会被越过。

实现记录排序时,移动的应是键连同卫星数据,而非只移动键。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 2 章《算法入门》2.1 节(`OEBPS/chapter002.xhtml`,图 2.1 与插入排序伪代码)。 - 结论依据:原文解释键与卫星数据共同组成记录,并以手牌和伪代码说明有序前缀与元素移动;相等键不被越过是由 `A[j] > key` 比较条件推得。 - 原始内容:Together, a key and satellite data form a record . - 原始内容:At all times, the cards held in your left hand are sorted, and these cards were originally the top cards of the pile on the table.