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] 表示"new"数组的项目 i。 请注意，未使用 v[0]。 n小于100000，不等于。

Answer 1

您正在比较存储在 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 的元素>。这就是为什么您至少还应该使用 vec

的元素交换 z 的元素或 z 的索引元素

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;
...