查找数组最大最小元素时快速排序算法运行异常的问题排查

• 核心错误是quickSort和partition函数的vector<int> arr参数采用值传递：C++值传递时会生成实参的副本，函数内对arr的所有修改都只作用在副本上，不会影响main函数里的原始数组，排序自然不会生效。
• 次要逻辑优化点：partition的循环遍历范围可以调整为j < high，因为pivot是arr[high]，不需要和自身比较。

#include <iostream>
#include <vector>

using namespace std;

void swap(int *a, int *b){
    int t = *a;
    *a = *b;
    *b = t;
}

// 参数改为引用传递，&表示直接操作原数组
int partition(vector<int>& arr ,int low, int high){
    int pivot = arr[high];
    int i = low-1;
    // 循环到high-1即可，跳过pivot自身
    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(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()
{
    vector<int> arr = {5,2,3,4,1};
    int arr_size = arr.size();
    quickSort(arr,0,arr_size-1);
    cout<<"数组的最小值和最大值为：\n";
    cout<<arr[0]<<" "<<arr[arr_size-1];

    return 0;
}

如果只需要获取数组的最大、最小值，不需要完全排序：仅需一次遍历数组就能拿到结果，时间复杂度为O(n)，远低于快速排序的O(nlogn)，实现逻辑更简单也不会出现排序相关的bug。

内容的提问来源于stack exchange，提问作者Ankit Negi