c++快速排序多输出了一个0，少了后面的一个数

Question

c++快速排序多输出了一个0，少了后面的一个数是怎么回事？
测试样例：
4
1 3 2 3
输出：
0 1 2 3
代码：

#include <bits/stdc++.h>
using namespace std;
int a[1005];
void quicksort(int l,int r)
{
    if(l>=r)
    {
        return;
    }
    int pivot=a[l+rand()%(r-l+1)];
    int i=l-1,idx=l,j=r+1;
    while(idx<j)
    {
        if(a[idx]<pivot)
        {
            swap(a[idx++],a[++i]);
        }
        else if(a[idx]>pivot)
        {
            swap(a[idx],a[--j]);
        }
        else
        {
            idx++;
        }
    }
    quicksort(l,i);
    quicksort(j,r);
}
int main()
{
    srand(time(NULL));
    int n;
    cin >> n;
    for(int i=1;i<n;i++)
    {
        cin >> a[i];
    }
    quicksort(1,n);
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

请各位回答！谢谢！

Answer 1

该回答引用自GPT-deepseek, 由博主 GISer Liu 编写：

问题分析

用户在使用C++实现快速排序时遇到了两个问题：

1. 多输出了一个0。
2. 少输出了后面的一个数。

问题定位

1. 多输出了一个0：

   • 代码中数组 a 的初始化可能存在问题，导致未赋值的元素默认为0。
   • 在输出数组时，可能会输出未赋值的元素。

2. 少输出了后面的一个数：

   • 在输入数组元素时，循环条件 i<n 导致最后一个元素没有被读取。

解决方案

修改代码

1. 修正输入循环条件：

   • 将 for(int i=1;i<n;i++) 修改为 for(int i=1;i<=n;i++)，确保所有元素都被读取。

2. 修正输出循环条件：

   • 将 for(int i=1;i<=n;i++) 修改为 for(int i=1;i<=n;i++)，确保所有元素都被输出。

3. 初始化数组：

   • 确保数组 a 的初始化不会导致未赋值的元素默认为0。

修改后的代码

#include <bits/stdc++.h>
using namespace std;
int a[1005];
void quicksort(int l,int r)
{
    if(l>=r)
    {
        return;
    }
    int pivot=a[l+rand()%(r-l+1)];
    int i=l-1,idx=l,j=r+1;
    while(idx<j)
    {
        if(a[idx]<pivot)
        {
            swap(a[idx++],a[++i]);
        }
        else if(a[idx]>pivot)
        {
            swap(a[idx],a[--j]);
        }
        else
        {
            idx++;
        }
    }
    quicksort(l,i);
    quicksort(j,r);
}
int main()
{
    srand(time(NULL));
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) // 修改输入循环条件
    {
        cin >> a[i];
    }
    quicksort(1,n);
    for(int i=1;i<=n;i++) // 修改输出循环条件
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

解释

1. 输入循环条件修改：

   • 将 for(int i=1;i<n;i++) 修改为 for(int i=1;i<=n;i++)，确保所有元素都被读取。

2. 输出循环条件修改：

   • 将 for(int i=1;i<=n;i++) 修改为 for(int i=1;i<=n;i++)，确保所有元素都被输出。

通过上述修改，可以确保所有输入的元素都被正确读取和输出，避免了多输出一个0和少输出一个数的问题。

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑