C语言C++ 排序算法 题

Question

acwing基础算法课上面的，题目是这样

我一开始没看讲解，写出来是这样

#include<stdio.h>

const int N=100010;


void sort(int q[],int l,int r)
{
    int i,j;

    int num=0;
    for(i=l;i<r;i++)
    {
        for(j=i+1;j<=r;j++)
        {
            if(q[i]>q[j])
            num++;
        }
    }
    printf("%d\n",num);
}

int main()
{
    int n;
    scanf("%d",&n);
    int s[N];
    int i;
    for(i=0;i<n;i++)
    scanf("%d",s[i]);

    sort(s,0,n-1);

    return 0;
}

这段代码可以运行但是不能输出结果，抛开题目来看不知道这段代码本身哪里出错了
还有就是我没有用排序，它不用排序也可以做吧？上面的思路把 i j 当成两个指针遍历数组。

原题给的解答是这样

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int a[N], tmp[N];

LL merge_sort(int q[], int l, int r)
{
    if (l >= r) return 0;

    int mid = l + r >> 1;

    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else
        {
            res += mid - i + 1;
            tmp[k ++ ] = q[j ++ ];
        }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    cout << merge_sort(a, 0, n - 1) << endl;

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/39791/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Answer 1

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

根据你描述的问题，你提供了两段代码，第一段代码有一些错误，无法输出结果。首先我们来看看第一段代码：
cCopy code

#include<stdio.h>
const int N=100010;
void sort(int q[],int l,int r) {
int i,j;
int num=0;
for(i=l;i<r;i++)
{
for(j=i+1;j<=r;j++)
{
if(q[i]>q[j])
num++;
}
}
printf("%d\n",num);
}
int main() {
int n;
scanf("%d",&n);
int s[N];
int i;
for(i=0;i<n;i++)
scanf("%d",s[i]);
sort(s,0,n-1);
return 0;
}

在这段代码中，你尝试通过两个循环来统计逆序对的数量，但是在输入数组时有一个小错误。应该是 scanf("%d", &s[i]); 而不是
scanf("%d", s[i]);。因为你需要将输入的整数存储到数组 s 的各个元素中，而不是直接传递给 scanf 函数。修改后的代码如下：
cCopy code

#include<stdio.h>
const int N=100010;
void sort(int q[],int l,int r) {
int i,j;
int num=0;
for(i=l;i<r;i++)
{
for(j=i+1;j<=r;j++)
{
if(q[i]>q[j])
num++;
}
}
printf("%d\n",num);
}
int main() {
int n;
scanf("%d",&n);
int s[N];
int i;
for(i=0;i<n;i++)
scanf("%d", &s[i]); // 修改这里
sort(s,0,n-1);
return 0;
}

接下来，你提供了第二段代码，这段代码使用了归并排序来统计逆序对的数量，是一个更高效的算法。这段代码是正确的，并且会输出正确的结果。
如果你对第一段代码的错误有进一步的疑问，或者有其他问题需要解答，请随时提出。

如果该回答解决了您的问题，请采纳！如果没有，请参考以下方案进行修订