原地算法（in-place algorithm）

In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. In-place algorithm updates input sequence only through replacement or swapping of elements. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.——摘自原地算法的维基百科

一句话总结就是: 原地算法不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入的一种算法操作。

维基百科中的伪代码示例：

假设要将具有 n 项内容的数组 a 翻转过来。一种看似简单的方法是创建一个大小相等的新数组，用适当的顺序填充副本，然后再删除：

 function reverse(a[0..n-1])
     allocate b[0..n-1]  # 额外设定一个数组
     for i from 0 to n-1 # 从 0 到 n-1 遍历数组 a
         b[n -1 - i] := a[i] 
     return b

这种方法虽然简单，但是需要 O(n) 的额外空间以使数组 a 和 b 同时可用。此外，分配存储空间和释放存储空间通常是缓慢的操作。如果我们不再需要数组 a 的话，可使用原地算法，用它自己翻转的内容来覆盖掉原先的内容。这样，无论数组有多大，它都只需要辅助变量 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

这样既节省了存储器空间又加快了运算速度。

原地算法的 Python 实现：

def reverse(a):
    """
    :param a: list
    :return: list
    """
    n = len(a)-1
    tmp = list()
    for i in range(int(n/2)):
        tmp = a[i]
        a[i] = a[n-i]
        a[n-i] = tmp
    print(a)

    return a



if __name__ == '__main__':
   a = [1, 2, 3, 4, 5, 6]
   reverse(a)


-------------------------------
[6, 5, 3, 4, 2, 1]