空间复杂度问题

Question

可能的重复：
关于数组中的就地合并

我有一个数组，其中数组的前半部分和后半部分已排序，例如

A[] = "2 4 7 1 5 20"

否，如何以 O(1) 空间复杂度对整个数组进行排序？

问候， 米敦

Answer 1

查看此列表，并从具有以下功能的算法中进行选择： “内存”列中的“1”。如果您唯一的要求是恒定的辅助空间，没有其他效率要求，则数组已经具有某种顺序的事实是无关紧要的。

Answer 2

这对我来说是一种尖叫的合并排序（为了时间效率），我认为它没有一个很好的就地算法（O(1) 空间）。您可以查看这个问题 - 地方合并排序。

我同意 Ani 的观点，如果你确实需要 O(1) 空间，那么使用 快速排序。

Answer 3

使用伪代码，这是一个就地两个堆栈合并。

i <- 0
mid <- A.size/2
while i < mid:
  if A[i] > A[i+mid] then
    swap A[i] and A[i+mid]
  i <- i + 1

它通过维持以下不变量来工作（应该工作）： A[1..mid] 和 A[mid..n] 已排序，并且 A[1..i] 包含的元素严格小于 A[ 中包含的元素中..n]。我可能搞砸了细节，但这是基本想法。

Answer 4

我（当然）可能是错的，但我猜任何只需要 O(1) 空间的东西也将具有 O(N²) 复杂性。尽管如此，我认为您可以比仅仅应用普通插入排序做得更好（一点）。

template <class T, class inIter>
void insert(T t, inIter point, inIter end) {
    inIter right = point;
    ++right;
    while (right != end && *right < t) 
        *point++ = *right++;
    *point = t;
}

void ipmerge(std::vector<int> &A) {
    size_t right = A.size()/2;
    for (size_t left = 0; left < A.size()/2;++left) {
        if (A[right] < A[left]) {
            int t = A[left];
            A[left] = A[right];
            insert(t, A.begin()+right, A.end());
        }
        if (left+1 == right)
            ++right;
    }
}