Insertion Sort

Definition / 释义

插入排序：一种简单直观的排序算法。它从左到右遍历序列，把当前元素像“插牌”一样插入到前面已经排好序的子序列中的正确位置。常用于数据量较小或序列“几乎有序”的场景。（除基本含义外，在工程实践中也常指其在混合排序中的小规模子过程。）

Pronunciation / 发音

/ɪnˈsɜːrʃən sɔːrt/

Examples / 例句

Insertion sort is easy to implement for small arrays.
插入排序在处理小数组时很容易实现。

Although insertion sort is (O(n^2)) in the worst case, it can be efficient when the input is nearly sorted and is often used inside hybrid sorting algorithms.
尽管插入排序在最坏情况下是 (O(n^2))，但当输入几乎有序时它可能很高效，并且常被用在混合排序算法的内部。

Etymology / 词源

insertion 来自 insert（插入），源于拉丁语 inserere（把……放入/嵌入）；sort 来自法语 sortir（按类别分配、整理）的相关词源传统，现代英语中固定为“排序/分类”。合起来字面意思就是“用插入方式完成排序”。

Related Words / 相关词

• Bubble Sort
• Selection Sort
• Merge Sort
• Quick Sort
• Heap Sort
• Stable
• In-Place
• Hybrid Sort

Literary Works / 文学作品

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein），常用插入排序作为基础算法与渐进分析的入门示例。
• The Art of Computer Programming, Volume 3: Sorting and Searching（Donald E. Knuth），系统讨论排序与查找，其中包含插入类方法的分析与变体。
• Algorithms（Robert Sedgewick & Kevin Wayne），在排序章节中介绍并对比插入排序与其他基础排序方法。