Insertion Algorithm

Definition / 定义

插入算法：一类通过“把新元素插入到已有结构中的合适位置”来完成任务的算法思路。最常见的用法是在排序中，指插入排序（insertion sort）的核心方法：从左到右逐个取元素，把它插入到前面已经排好序的部分中，从而逐步得到有序序列。（在其他场景也可指把数据插入数据结构的过程与规则。）

Pronunciation / 发音

/ɪnˈsɝːʃən ˈælɡəˌrɪðəm/

Examples / 例句

The insertion algorithm works well for small or nearly sorted lists.
插入算法对小规模或几乎已排好序的列表效果很好。

In our system, an insertion algorithm places each new record into the correct position to keep the index ordered.
在我们的系统中，插入算法会把每条新记录放到正确位置，以保持索引有序。

Etymology / 词源

insertion 来自拉丁语 insertio（“插入、嵌入”），核心含义是“把某物放进/放入其中”；algorithm 源自阿拉伯数学家 al-Khwārizmī（花剌子密） 的名字，经由拉丁化形式传播到欧洲语言中，逐渐演变为“解决问题的步骤/方法”。合起来 insertion algorithm 就是“以插入为主要操作步骤的算法”。

Related Words / 相关词

• Insertion
• Insert
• Insertion Sort
• Sorting Algorithm
• Merge Sort
• Quick Sort
• Binary Search
• Data Structure

Literary Works / 文学作品举例

• The Art of Computer Programming, Volume 3: Sorting and Searching（Donald E. Knuth）：在排序与查找专题中系统讨论插入类方法与相关分析。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein；常称 CLRS）：以插入排序作为入门示例，讲解“通过插入逐步维护有序”的算法思想。
• Algorithms（Robert Sedgewick & Kevin Wayne）：在基础排序章节介绍插入排序及其适用场景（如“小规模/近乎有序数据”）。