c - 冒泡排序的一个错误

Question

我想对一个 2*n 矩阵进行排序，n 在输入中给出。编写一个程序来输出一个矩阵。这是要求：

1. 第一列必须按 ASC 排序，并且
2. 如果可能，DESC 中的第二列。

例如，设 n = 5，则矩阵为

3 4
1 2
3 5
1 6
7 3

结果应该是

1 6
1 2
3 5
3 4
7 3

所以我写下这样的代码。第一行输入值 n，接下来的行如上。

#include <stdio.h>
#define TWO_16 65536
#define TWO_15 32768

int v[100000][2];
int z[100000];
int vec[100000];
int n;


int main()
{
    int i, j;
    scanf ("%d", &n);   // give the value of n;
    for (i = 1; i <= n; i++)    // filling the matrix;
    {
        scanf ("%d%d", &v[i][0], &v[i][1]);
        z[i] = TWO_16 * v[i][0] + TWO_15 - v[i][1];
        vec[i] = i;
    }
    for (i = 1; i <= n; i++)
        for (j = 1; j <= i; j++)
        {
            if (z[j] > z[i])
            {
                int t = vec[i];
                vec[i] = vec[j];
                vec[j] = t;
            }
        }

    for (i = 1; i <= n; i++)   // output the matrix
        printf("%d %d\n",v[vec[i]][0],v[vec[i]][1]);
    return 0;
}

但是在 gcc 中，输出是

1 6
3 5
3 4
1 2
7 3

更重要的是，当输入的第一行改为“1 2”，第二行改为“3 4”时，结果也发生了变化。

我的代码有什么问题？

附加信息：

我使用z[]是因为我使用了一个满足这个问题要求的函数，所以我可以简单地对它们进行排序。并vec[]存储原始索引，因为移动数组可能会花费大量时间。所以v[vec[i]][0]意味着“新”数组的 item i。请注意，不使用 v[0]。n 小于 100000，不等于。

Answer 1

数组索引从 0 开始，所以你的 for cicles 必须从 0 开始

if (z[j] > z[i]): 你想排序v，但你正在比较z和排序vec。通过排序vec和比较z冒泡排序是行不通的。您必须使用相同的数组。

Answer 2

您正在比较存储在 中的值z[]，但交换 中的元素vec。因此，当您处于起步阶段时：

i  vec      z
------------------
1   1     z[1]
2   2     z[2]
3   3     z[3]
...   

例如，在将 2 与 3 交换之后

i  vec      z
------------------
1   1     z[1]
2   3     z[2]
3   2     z[3]
...

您将在 和 之间进行不正确的vec映射z。

因此，在另一次迭代中，您将再次与 进行比较z[2]，z[3]并且必须再次交换vec. 这就是为什么您至少还应该使用 z 的元素交换zz 的元素或索引元素vec

i  vec      z
------------------
1   1    z[vec[1]] = z[1]
2   3    z[vec[2]] = z[3]
3   2    z[vec[3]] = z[2]
...

添加这个应该可以解决问题

...
int t = vec[i];
vec[i] = vec[j];
vec[j] = t;
//Add this also when swapping vec
t = z[i];
z[i] = z[j];
z[j] = t;
...