std::vector版快速排序无效：原因解析及修复方案

我一眼就瞅到几个关键问题，导致排序后原数组完全没变化：

• 传值传递导致修改无效：你的quickSort和printArray函数里，vector<int> array是按值传递的——也就是说，每次调用函数都会创建一个原vector的副本，函数里做的排序操作全是在这个副本上折腾，原数组根本没被碰过！这就像你拿一份文件复印件改半天，原件当然纹丝不动。
• vector长度计算错误：sizeof(array)/sizeof(array[0])这是给C风格数组算长度的写法，vector是C++容器，sizeof(array)得到的是vector对象本身的内存大小（不是元素总字节数），所以你算出来的n是错的，应该用array.size()来获取元素个数。
• 排序边界参数错误：调用quickSort(array, 0, n)的时候，high参数传了n，但vector的索引是从0到n-1，传n会让函数里访问array[j]时越界，属于未定义行为，运气差的话程序直接崩了。

把参数改成引用，修正长度计算和边界，代码就正常了：

#include <iostream>
#include <vector>
using namespace std;

// 改成传const引用，避免拷贝，同时保证不修改原数组
void printArray(const vector<int>& array) {
    for (int num : array)
        cout << num << endl;
}

// 传引用，这样排序操作直接作用在原vector上
void quickSort(vector<int>& array, int low, int high) {
    int i = low;
    int j = high;
    int pivot = array[(i + j) / 2];
    int temp;
    while (i <= j) {
        while (array[i] < pivot)
            i++;
        while (array[j] > pivot)
            j--;
        if (i <= j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
    }
    if (j > low)
        quickSort(array, low, j);
    if (i < high)
        quickSort(array, i, high);
}

int main() {
    vector<int> array = {95, 45, 48, 98, 1, 485, 65, 478, 1, 2325};
    // 用vector的size()获取元素个数，转成int适配函数参数
    int n = array.size();
    cout << "Before Quick Sort :" << endl;
    printArray(array);
    // high参数传n-1，对应最后一个元素的索引
    quickSort(array, 0, n - 1);
    cout << "After Quick Sort :" << endl;
    printArray(array);
    return 0;
}

• 用范围for循环替代传统索引循环，代码更简洁易读（比如printArray里的写法）
• 尽量避免using namespace std;，在大型项目里容易引发命名冲突，小demo里倒无所谓
• pivot的选择可以优化成三数取中法，避免极端情况下的最坏时间复杂度

内容的提问来源于stack exchange，提问作者Tsz Yee Ha