我试图理解不同排序算法的空间复杂度。
http://bigocheatsheet.com/?goback=.gde_98713_member_241501229
从上面的链接中我发现了复杂性。
气泡排序、插入和选择排序为O（1）
其中，快速排序为o（log（n））而合并排序为o（n）。
我们实际上没有在任何算法中分配额外的内存。
那么，当我们使用同一个数组对它们进行排序时，为什么空间复杂度不同呢？
最佳答案
运行代码时，内存分配有两种方式：
隐式地，在设置函数调用时。
显式地，当你创建内存块时。
快速排序是内存隐式使用的一个很好的例子当我在做一个快速排序时，在最坏的情况下，我递归地称自己为O(n)次，在平均情况下称自己为O(log(n))。每个递归调用都需要O(1)空间来跟踪，导致O(n)最坏情况和O(log(n))平均情况。
mergesort是显式使用内存的一个很好的例子。我获取两个已排序的数据块，创建一个放置合并的位置，然后从这两个数据块合并到该合并中创建放置合并的位置是O(n)数据。
要进入O(1)内存，您需要既不分配内存，也不递归调用自己这适用于所有气泡、插入和选择排序。