我试图了解不同排序算法的空间复杂性。
http://bigocheatsheet.com/?goback=.gde_98713_member_241501229 从上面的链接我发现冒泡排序，插入和选择排序的复杂性是O（1） 快速排序为O（log（n）），合并排序为O（n）。
我们实际上并没有在任何算法中分配额外的内存。那么当我们使用相同的数组对它们进行排序时，为什么空间复杂性会有所不同？
运行代码时，内存分配方式有两种：
Quicksort是隐式使用内存的一个很好的例子。虽然我正在做一个快速排序，但在最糟糕的情况下，我会递归地称自己为O(n)，平均情况下是O(log(n))。这些递归调用每个都需要O(1)空间来跟踪，导致O(n)最坏情况和O(log(n))平均情况。
Mergesort是显式使用内存的一个很好的例子。我获取两个排序数据块，创建一个放置合并的位置，然后从这两个合并到该合并。创建放置合并的位置是O(n)数据。
要了解O(1)内存，你需要不分配内存，而不是递归调用自己。所有泡沫，插入和选择排序都是如此。
重要的是要记住，有很多不同的方法来实现这些算法，每个不同的实现都有不同的相关空间复杂性。
让我们从合并排序开始。数组上mergesort的最常见实现是通过分配一个外部缓冲区来实现各个范围的合并。这需要空间来容纳数组的所有元素，这需要额外的空间Θ（n）。但是，您也可以为每个合并使用就地合并，这意味着您需要的唯一额外空间将是递归调用的堆栈帧的空间，将空间复杂度降低到Θ（log n），但是通过一个大的常数因子增加算法的运行时间。您也可以使用就地合并来进行自下而上的合并，这只需要O（1）额外空间但具有更高的常数因子。
另一方面，如果您要合并排序链接列表，那么空间复杂性将会大不相同。您可以在空间O（1）中合并链接列表，因为元素本身可以轻松地重新连接。这意味着合并排序链表的空间复杂度是来自存储递归调用的堆栈帧所需空间的Θ（log n）。
让我们看看quicksort作为另一个例子。 Quicksort通常不会分配任何外部内存，但它确实需要空间用于它使用的堆栈帧。如果枢轴总是最终成为数组的最大或最小元素，那么快速排序的简单实现可能在最坏情况下需要空间Θ（n），因为在这种情况下，您在大小为n的数组上递归调用函数 - 1，n - 2，n - 3等。但是，你可以执行一个标准的优化，基本上是尾部调用消除：你在数组的两半中较小的一半上递归调用quicksort，然后重用来自目前要求更大的一半。这意味着您只为大小最多n / 2，然后是n / 4，然后是n / 8等子阵列的递归调用分配新内存，因此空间使用率下降到O（log n）。
我假设我们正在排序的数组是通过引用传递的，我假设数组的空间不计入空间复杂度分析。
快速排序的空间复杂性可以通过巧妙的实现来实现O(n)（以及随机快速排序的预期O(log n)）：例如不要复制整个子数组，而只是传递索引。
快速排序的O(n)来自这样一个事实，即“嵌套”递归调用的数量可以是O(n)：想想如果你继续为枢轴做出不幸的选择会发生什么。虽然每个堆栈帧占用O(1)空间，但可以有O(n)堆栈帧。如果我们谈论随机快速排序，预期的深度（即预期的堆栈空间）是O(log n)。
对于合并排序，我希望空间复杂度为O(log n)，因为你最多使用O(log n)“嵌套”递归调用。
您引用的结果也会计算数组占用的空间：然后合并排序的时间复杂度为堆栈空间的O(log n)加上数组的O(n)，这意味着O(n)总空间复杂度。快速排序是O(n)+O(n)=O(n)。