面试题：C++ 优化归并排序空间复杂度

优化思路

传统归并排序空间复杂度分析：传统归并排序在合并过程中，需要额外开辟与原数组大小相同的辅助数组，用于暂存合并结果，所以空间复杂度为O(n)。
优化方向：通过采用原地归并的方式，减少额外空间的使用。原地归并并不需要开辟与原数组同样大小的辅助数组，而是在原数组的基础上进行操作，在合并子数组时，巧妙地利用原数组的空闲空间来存储临时结果，从而降低空间复杂度。

实现过程

#include <iostream>
#include <vector>

// 合并两个有序子数组，实现原地归并
void inplaceMerge(std::vector<int>& arr, int left, int mid, int right) {
    // 找到最小的需要移动的元素个数
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int minMoves = std::min(n1, n2);

    // 初始化临时数组，大小为最小移动元素个数
    std::vector<int> temp(minMoves);

    // 将左边数组的一部分复制到临时数组
    for (int i = 0; i < minMoves; i++) {
        temp[i] = arr[left + i];
    }

    int i = 0, j = mid + 1, k = left;
    while (i < minMoves && j <= right) {
        if (temp[i] <= arr[j]) {
            arr[k++] = temp[i++];
        }
        else {
            // 这里先移动右边的元素，使得左边的元素后移，腾出空间
            std::swap(arr[k], arr[j]);
            // 移动左边的元素，填补腾出的空间
            std::swap(arr[k], arr[mid - (minMoves - i - 1)]);
            k++;
            j++;
        }
    }

    // 将临时数组剩余元素放回原数组
    while (i < minMoves) {
        arr[k++] = temp[i++];
    }
}

// 优化后的归并排序
void optimizedMergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // 递归地对左右子数组进行排序
        optimizedMergeSort(arr, left, mid);
        optimizedMergeSort(arr, mid + 1, right);

        // 原地合并两个有序子数组
        inplaceMerge(arr, left, mid, right);
    }
}

你可以使用以下方式调用这个函数：

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    optimizedMergeSort(arr, 0, arr.size() - 1);

    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

空间复杂度分析

辅助空间：在优化后的归并排序中，inplaceMerge 函数使用了一个大小为 min(n1, n2) 的临时数组 temp，其中 n1 和 n2 分别是两个待合并子数组的长度。在整个归并过程中，最大的临时数组大小不会超过数组长度的一半，并且随着递归的进行，临时数组的空间是复用的。
递归栈空间：归并排序是递归实现的，递归深度为O(log n)，每一层递归需要的额外空间是常数级别的，所以递归栈空间复杂度为O(log n)。
总体空间复杂度：综合考虑，优化后的归并排序空间复杂度接近O(log n)。

星途面试题库

面试题：C++ 优化归并排序空间复杂度

知识考点

面试题答案

优化思路

实现过程

空间复杂度分析