知识卡片
有序前缀逐个接纳新元素
插入排序维护已排好序的前缀,每轮取出紧接其后的key,把前缀中比key大的项逐一右移,再把key放入留下的位置。02696-02697的issort以字节大小esize定位元素,用compare判断次序。
结构图:
flowchart TD
A[取下一项到临时key] --> B{左边仍有项且比key大}
B -->|是| C[该项右移并继续向左]
C --> B
B -->|否| D[把key放入空位]
D --> E{还有未处理项}
E -->|有| A
E -->|无| F[结束]
函数先malloc临时空间,失败返回-1;正常结束free后返回0。比较器与元素有效范围由调用方提供,代码没有通用参数检查;它只搬动esize字节,不深复制内部对象。
205已有序/未序并非一定两份独立存储,实际207用同一数组前缀与后缀分区,临时保存单个key即可移动现有项;没有额外结果数组不等于零临时空间。
207的02950初始[23,21,76,16,52,43]逐步变为[21,23,76,16,52,43]、再把16插到头,最终[16,21,23,43,52,76]。02951完整函数与第4章版本同一机制;只在compare>0时右移,等键不跨过先前等键,保留相对次序。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 有序前缀逐个接纳新元素
- · 插入排序的描述
- · 插入排序的实现与分析
原书出处 · 3 处
- · 查看原书依据
在一个有序的数据集中查找放置新元素的位置,并将新元素插入进去。在第12章完整描述了插入排序算法。插入排序的代码如示例4-1所示。 首先要知道,哪行代码会受要排序的数据量影响。我们看到代码中有一个嵌套循环,外层的迭代数从i到size-1,内层的迭代数从j-1到所要插入的新元素的正确位置。其他代码的运行
- · 查看原书依据
扫描已排好序的数据集,并将它插入有序集合合适的位置上。虽然乍一看,插入排序需要独立为有序和无序的元素集合预留足够的存储空间,但实际上它是不需要额外的存储空间的。 插入排序是一种较为简单的算法,但是它在处理大型数据集时并不高效。因为很明显,在决定将元素插入哪个位置之前,需要将被插入元素和有序数据集中的
- · 查看原书依据
变量i来向后查找元素将要放置的位置。当向后查找数据时,每个处于位置i的元素都要向右移动一位,以保证预留出足够的空间来插入新元素。一旦j到达无序数据集的尾部,data就是一个有序数据集了(见图12-1)。 图 12-1 插入排序 插入排序的时间复杂度关键在于它的嵌套循环部分。考虑到这一点,外部循环运行