In-place Algorithm

定义 Definition

in-place algorithm 指一种在运行过程中主要在原输入数据结构上直接完成计算的算法，所需的额外空间非常少（通常为 O(1) 或仅少量辅助变量）。常见于排序、数组/链表处理等场景。注：有时也会讨论“in-place”在不同教材中的严格程度差异（例如递归栈空间是否计入）。

发音 Pronunciation

/ˈɪn pleɪs ˈælɡəˌrɪðəm/

例句 Examples

An in-place algorithm sorts the array without allocating another array.
原地算法在不分配另一个数组的情况下对数组进行排序。

Because memory is limited, we chose an in-place algorithm that runs in linear time and uses only constant extra space.
由于内存有限，我们选择了一个原地算法：它线性时间运行，并且只使用常数级额外空间。

词源 Etymology

in-place 来自英语短语，字面意思是“在原处/就地”。在计算机科学语境中，它引申为“不搬移到新的存储位置、尽量利用原有数据结构完成操作”。algorithm 源自中世纪拉丁语 algoritmi，来自数学家 Al-Khwarizmi（花剌子密） 的名字，后来泛指“计算步骤/算法”。

相关词 Related Words

• In-Place
• Space Complexity
• Auxiliary Space
• Memory-Efficient
• Stable Sort
• Quicksort
• Heapsort

文学与经典作品 Literary Works

• Introduction to Algorithms（Thomas H. Cormen 等，“CLRS”）——讨论排序与空间开销时常提及 in-place。
• The Art of Computer Programming（Donald E. Knuth）——在排序与基础算法分析中涉及原地处理思想。
• Algorithms（Robert Sedgewick & Kevin Wayne）——讲解排序算法时对“是否原地”作对比说明。