面试题：C++ 优化快速排序实现

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

// 交换两个元素
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 划分函数
int partition(std::vector<int>& arr, int low, int high) {
    // 随机选择枢轴
    int pivotIndex = low + rand() % (high - low + 1);
    swap(arr[pivotIndex], arr[high]);
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// 快速排序
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    std::srand(std::time(nullptr));
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    quickSort(arr, 0, n - 1);

    std::cout << "排序后的数组: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

时间复杂度分析

平均情况：每次划分都能将数组大致分成两等份，时间复杂度为 $O(n \log n)$，其中 $n$ 是数组的元素个数。
最坏情况：尽管采用了随机化枢轴选择策略，理论上最坏情况仍可能出现，即每次划分的枢轴都是当前子数组的最大或最小元素，此时时间复杂度为 $O(n^2)$。但在实际应用中，这种最坏情况出现的概率极小。

空间复杂度分析

递归调用栈空间：快速排序是递归实现的，递归调用栈的深度决定了空间复杂度。在平均情况下，递归深度为 $\log n$，因此空间复杂度为 $O(\log n)$。在最坏情况下，递归深度达到 $n$，空间复杂度为 $O(n)$。
辅助空间：除了递归调用栈，代码中只使用了常数级别的额外空间（如交换时的临时变量等），因此辅助空间复杂度为 $O(1)$。总体空间复杂度取决于递归调用栈空间，平均为 $O(\log n)$，最坏为 $O(n)$。

星途面试题库

面试题：C++ 优化快速排序实现

知识考点

面试题答案

时间复杂度分析

空间复杂度分析