原地算法

给定一个包含 n 个元素的数组a，假设我们需要一个数组，它以相反的顺序保存相同的元素并处理原始元素。一种看似简单的方法是创建一个大小相等的新数组，复制a里的元素，然后删除a。

 function reverse(a[0..n - 1])
     allocate b[0..n - 1]     for i from 0 to n - 1
         b[n − 1 − i] := a[i]     return b

不幸的是，这需要0(n) 额外空间用于同时存储置数组的a和b。此外，分配和释放分配通常是缓慢的操作。因为我们不再需要a，我们可以使用原地算法，用它自己的反转来覆盖它，不管数组有多大，它只需要常量(2)的整数的辅助变量i和tmp。

 function reverse_in_place(a[0..n-1])     for i from 0 to floor((n-2)/2)
         tmp := a[i]
         a[i] := a[n − 1 − i]
         a[n − 1 − i] := tmp

另一个例子，许多排序算法使用原地算法将数组重新排列，包括: 冒泡排序, 梳子分类, 选择排序法, 插入排序, 堆排序，和 希尔排序。这些算法只需要几个指针，所以它们的空间复杂度是O(log n)。^[1]

快速排序对要排序的数据进行原地操作。然而，快速排序需要O(log n) 堆栈空间指针以跟踪其分治法策略。因此，快速排序需要O(log² n) 额外的空间。虽然这种非恒定空间在技术上使快速排序脱离了原地算法类别，但快速排序和其他算法只需要O(log n) 附加指针通常被认为是原地算法。

大多数选择算法也是原地的，尽管有一些在寻找最终的、大小不变的结果的过程中对输入数组进行了相当大的重新排列。

一些文本操作算法，例如Trim和反转可以通过原地完成。

在计算复杂性理论中，原地算法的严格定义包括所有具有O(1)空间复杂度的算法，类 DSPACE(1)。这门课非常有限；它等于正规语言.^[2] 事实上，它甚至不包括上面列出的任何例子。

我们通常在 L，需要操作的问题类别(日志 n)额外空间到位。这个类更符合实际定义，因为它允许大小为n的数字作为指针或索引。然而，由于快速排序的递归调用，这个扩展的定义仍然不包括快速排序。

用L识别原地算法有一些有趣的含义；例如，这意味着有一个(相当复杂的)原地算法来确定无向图,^[3] 需要操作的问题(n)使用典型算法的额外空间，例如深度优先搜索 (每个节点的访问位)。这反过来又产生了针对诸如确定图形是否双方的或者测试两个图表是否具有相同数量的连接组件。

在许多情况下，通过使用随机化算法，一个算法的空间需求可以被极度地裁减掉。例如，我们希望知道一个有n个顶点（vertices）的图形中的两个顶点是否位于图中同一个连接组件。没有已知的简单的、确定的、原地的算法来确定这一点，但是如果我们简单地从一个顶点开始并执行随机游走大约20个n³ 步骤，如果它在同一个组件中，我们偶然发现另一个顶点的可能性非常高。类似地，也有简单的随机原地算法用于质数测试，例如米勒-拉宾素性检验，还有简单的原地随机化因子分解算法，例如波拉德ρ算法。

函数式编程语言经常不鼓励或不支持会覆盖数据的原地算法，因为这是一种副作用的类型；相反，它们只允许构建新数据。然而，好的函数式语言编译器通常会识别出一个与现有对象非常相似的对象是什么时候创建的，然后旧的对象被丢弃，并且会将它优化成一个简单的“幕后”变异。

注意，原则上可以仔细构建不修改数据的原地算法(除非数据不再被使用)，但实际上很少这样做。