知识卡片
插入排序维护有序前缀
插入排序每轮取出当前位置的键,向右移动有序前缀中更大的键,再把它放入空位。
比较条件为“大于”时,相等的键不会被越过。
实现记录排序时,移动的应是键连同卫星数据,而非只移动键。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第2章 算法入门 · 查看原书依据
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.
参考来源
- 位置:《算法导论(第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.