快速排序（QuickSort）处理负元素时出现排序异常的问题

你的快排代码在处理含负元素数组时出现异常，核心原因是递归过程中未提前判断子数组长度，导致median3函数在子数组过小时访问越界内存，进而篡改数组元素。

当子数组长度小于3（比如left == right，或者right = left+1）时，median3里的Swap(&A[center], &A[right-1])会访问数组的非法位置（比如right=left时，right-1 = left-1，超出数组左边界），这会破坏数组外的内存，最终反映到数组里就是元素被篡改、排序错误。全正数时可能刚好没触发明显的错误表现，但本质上代码是不安全的。

修复后的完整代码 #

#include<stdio.h>

int median3(int A[],int left,int right);
void Swap(int *a,int *b);
void qSort(int A[],int left,int right);
void quickSort(int A[],int N);

int main(){
    int a[] = {-99,-11,1,3,55,9,12,3,4,90,0,12,32};
    const int length = sizeof(a)/sizeof(a[0]);
    quickSort(a,length);
    for(int i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    return 0 ;
}

/*
median3 is to find the pivot between 3 elements(find the median)
*/
int median3(int A[],int left,int right){
    int center = (left+right)/2;
    if(A[left]>A[center])
        Swap(&A[left],&A[center]);
    if(A[left]>A[right])
        Swap(&A[left],&A[right]);
    if(A[center]>A[right])
        Swap(&A[center],&A[right]);
    Swap(&A[center],&A[right-1]);
    return A[right-1];
}

void Swap(int *a,int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void qSort(int A[],int left,int right){
    // 递归终止条件：子数组长度为0或1，直接返回
    if(left >= right)
        return;
    
    // 子数组长度为2时，直接比较交换，无需调用median3
    if(right - left +1 ==2){
        if(A[left]>A[right])
            Swap(&A[left],&A[right]);
        return;
    }

    int pivot = median3(A,left,right);
    int i = left;
    int j = right-1;

    while(1){
        while(A[++i]<pivot){}
        while(A[--j]>pivot){}
        if(i<j){
            Swap(&A[i],&A[j]);
        }else{
            break;
        }
    }
    Swap(&A[i],&A[right-1]);
    qSort(A,left,i-1);
    qSort(A,i+1,right);
}

void quickSort(int A[],int N){
    qSort(A,0,N-1);
}

关键修改点 #

• 添加递归终止条件：在qSort开头判断left >= right时直接返回，避免无效递归和越界操作。
• 处理短子数组：当子数组长度为2时，直接比较交换后返回，不再调用median3，防止right-1越界。
• 移除原代码中多余的if(i<j)判断：因为已经提前处理了短数组，进入循环时i必然小于j。

修复后运行测试数组，输出应为：-99 -11 0 1 3 3 4 9 12 12 32 55 90，排序正常且无元素篡改。

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