C++单vector参数单方法快速排序实现问题求助

嘿，我来帮你搞定这个快速排序的问题！

首先得纠正一个关键误解：你最初怀疑的if(i <= j)这行其实没问题——这里比较的就是索引，不是元素值！这一步是用来判断左右指针有没有交叉，是快速排序双指针法里的核心逻辑之一。你改成比较元素值后出现内存爆涨、程序不终止，大概率是触发了死循环，因为指针没法正确移动，递归也停不下来了。

接下来，咱们聊聊怎么把快速排序做成单个方法，不用拆分分区和排序函数。其实很简单，把分区的逻辑直接嵌入递归的排序函数里就行，下面给你一个完整的示例代码：

#include <vector>
#include <algorithm> // 用于std::swap

void quickSort(std::vector<int>& nums, int left, int right) {
    // 递归终止条件：子数组只有一个或没有元素时不用排序
    if (left >= right) {
        return;
    }

    // 选基准元素，这里选中间位置的元素，避免有序数组的最坏情况
    int pivot = nums[(left + right) / 2];
    int i = left, j = right;

    // 双指针移动，找需要交换的元素
    while (i <= j) {
        // 左指针找比基准大的元素
        while (nums[i] < pivot) {
            i++;
        }
        // 右指针找比基准小的元素
        while (nums[j] > pivot) {
            j--;
        }

        // 如果指针还没交叉，交换元素，然后移动指针
        if (i <= j) {
            std::swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }

    // 递归排序左右两个子数组
    quickSort(nums, left, j);
    quickSort(nums, i, right);
}

// 对外的简化接口，不用手动传左右边界
void quickSort(std::vector<int>& nums) {
    if (!nums.empty()) {
        quickSort(nums, 0, nums.size() - 1);
    }
}

关键细节说明： #

• 双指针的移动逻辑：i从左往右找第一个大于等于基准的元素，j从右往左找第一个小于等于基准的元素，找到后如果i <= j就交换，然后指针继续移动——这一步的i <= j是判断指针是否还在有效范围内，绝对不能改成元素值比较！
• 基准元素选中间位置，比选第一个元素更稳妥，能避免数组已经有序时的O(n²)最坏时间复杂度。
• 递归的边界是left >= right，确保子数组长度为1时停止递归，避免无限递归。

你之前遇到的内存问题，就是因为错误修改了if(i <= j)的判断逻辑，导致指针无法正常推进，递归一直重复调用，栈内存被持续占用，最终程序卡死。把这部分改回索引比较，再对照上面的逻辑调整双指针的移动循环，应该就能解决问题了。

内容的提问来源于stack exchange，提问作者William Machado