In-place sort

Definition / 定义

in-place sort（原地排序）：一种排序方法，在不使用（或只使用极少）额外内存的情况下，直接在原数据结构（常见为数组）内部交换元素完成排序。
（在算法语境中常与 out-of-place sort“非原地排序”对比。）

Pronunciation / 发音

/ˌɪnˈpleɪs sɔːrt/

Examples / 例句

Insertion sort is an in-place sort.
插入排序是一种原地排序。

To reduce memory use, the engineer chose an in-place sort that rearranges the array without allocating extra storage.
为了减少内存占用，工程师选择了原地排序，它在不分配额外存储的情况下重排数组。

Etymology / 词源

in-place 来自计算机领域的常用表达，字面意思是“在原位置”，引申为“直接在原数据所在位置进行修改/处理”。sort 源自古法语 sortir（“分类、排列”相关含义）及其后续演变，在英语中固定为“排序、分类”。组合成 in-place sort，强调排序过程中数据“就地”被重排。

Related Words / 相关词

• In-place
• Out-of-place
• Stable Sort
• Unstable Sort
• Quicksort
• Heapsort
• Partition

Literary Works / 文学与著作示例

• _Introduction to Algorithms_（《算法导论》, Cormen et al.）：讨论排序算法的空间复杂度时常提到“in-place”性质。
• _The Art of Computer Programming_（《计算机程序设计艺术》, Donald Knuth）：在排序与查找相关卷册中涉及原地重排与空间开销。
• _Algorithms_（《算法》, Robert Sedgewick & Kevin Wayne）：讲解快速排序、堆排序等时，会强调哪些算法是 in-place。