请问我这为啥会出错呢，输出全是0

Question

请问我这为啥会出错呢，输出全是0，给的范围应该是对的1e6+10,不知道是不是int错了，改成long报的错更多了。

#include <iostream>
using namespace std;

const int N= 1e6+10;

int n;
int q[N];

void quick_sort(int q[],int l,int r) 
{
    if(l==r) return;
    int x=q[l],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while (q[i]<x);
        do j--;while (q[j]>x);
        
        if(i<j) swap(q[i],q[j]);
    }
    //递归处理左右两段 
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++) printf("%d ", q[i]);
    return 0;
}

Answer 1

• 这个代码中，快速排序的终止条件是 if(l==r) return;，也就是如果左指针和右指针重合了，就直接退出函数。
• 但是你的代码中的数组下标是从 0 开始的，所以当左指针和右指针都为 0 时，就会退出函数。
• 因此，在调用递归函数的时候，就会发生终止条件，导致排序没有起到作用，结果输出全为 0。

为了解决这个问题，你可以将终止条件修改为左指针大于等于右指针，这样就不会发生终止条件，递归函数就可以正常执行。修改后的代码如下：

#include <iostream>
using namespace std;

const int N= 1e6+10;

int n;
int q[N];

void quick_sort(int q[],int l,int r) 
{
    if(l>=r) return; //修改终止条件
    int x=q[l],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while (q[i]<x);
        do j--;while (q[j]>x);

        if(i<j) swap(q[i],q[j]);
    }
    //递归处理左右两段 
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++) printf("%d ", q[i]);
    return 0;
}