c 快速排序不工作

Question

学习C，这是一个练习。

要求用户输入二维数组的维度。 然后用户输入该数组的值。 最后，程序必须能够将每一行从最低到最高排序并打印结果。

例如

输入：

2 2
13 11
13 11

应该打印：

11 13
11 13

但我的程序正在打印：

11 13
13 11

如果在我的代码中我声明了一个固定的数组大小，比如说矩阵 [2] [2] 并将所有代码更改为该数组维度，则该程序运行良好，但如果我声明矩阵[MAX][MAX]，因为我不知道数组的大小是多少，所以它给了我上面发布的输出。

这是因为我没有使用指针和内存分配吗？ （记住我还在学习C）。

这是我完成的代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000

/*Print the final two-dimensional array*/
void print( int a[MAX][MAX], int b[])
{
    int i,j;
    for (i=0; i<b[0]; i++)
    {
        for (j=0; j<b[1]; j++)
        {
            printf("%d", a[i][j]);
            if (j < b[1]-1)
            {
                printf(" ");
            }
        }
        printf("\n");
    }
}

/* Sort my array */
int Qsort (int v[MAX][MAX], int li, int ls)
{
    int j;
    if (li < ls)
    {
        j = order(v,li, ls);
        Qsort (v, li, j-1);
        Qsort (v, j+1, ls);
    }
    return v[MAX][MAX];
}


int order(int x[], int li, int ls)
{
    int a, down, up, temp;
    a=x[li]; down=li; up=ls;
    while (down<up)
    {
        while (x[down]<=a && down<ls)
            down ++;
        while (x[up]>a)
            up --;
        if (down < up)
        {
            temp=x[down];
            x[down]=x[up];
            x[up]=temp;
        }
    }
    x[li]=x[up];
    x[up]= a;
    return up;
}

int main()
{
    int i,j,size,jump,jump2;
    int tam[2];
    int matrix[MAX][MAX];

    /*Define rows and columms*/
    i=0;
    while (i<2)
    {
        scanf("%d", &tam[i]);
        i++;
    }

    /*Fill the array with the numbers the user inputs*/
    for (i=0; i<tam[0]; i++)
    {
        for (j=0; j<tam[1]; j++)
        {
            scanf("%d", &matrix[i][j]);
        }
    }

    size = tam[1];
    jump = 1;
    jump2 = 0;

    for(i=0;i<tam[0];i++)
    {
        Qsort (matrix,jump2, jump*size-1);
        jump++;
        jump2 = jump2 + size;

    }

    print (matrix,tam);

    return 0;
}

谢谢，

Favolas

Answer 1

看起来您正在一遍又一遍地对第一行进行排序。您只想将单个列传递给 Qsort，因此应声明它：

Qsort(int v[MAX], int li, int ls)

在主函数中，只需对每个连续行调用 Qsort：

Qsort(matrix[i], 0, size-1);

Answer 2

#define MAX 1000
int matrix[MAX][MAX];

/*Fill the array with the numbers the user inputs*/
for (i=0; i<tam[0]; i++)
{
    for (j=0; j<tam[1]; j++)
    {
        scanf("%d", &matrix[i][j]);
    }
}

根据此矩阵定义，您的 2x2 数据最终会出现在 matrix[0][0]、matrix[0][1]、matrix[1][0 ] 和矩阵[1][1]。没有什么令人惊讶的，但是当被视为单元格的线性列表时，填充的单元格是：（

base_address + 0
base_address + 1
base_address + 1000
base_address + 1001

当然，其中base_address = &matrix[0][0]。）

您没有办法代码来检查 Qsort() 代码中的后两个单元格。

这里有几个结论可以得出。

• 了解如何打印良好的诊断信息。
• 在进入例程时打印数据。 （如果您在 Qsort() 的入口处打印了数组，您会发现您没有认为应该处理的值。这可以确保您知道如何访问数据准确。）
• 选择好的测试数据。不要在测试数据中重复数字（例如，11、12、13、14 是一组更好的输入）。
• 了解二维数组及其切片。

考虑一下矩阵[4][7]的图：

      0   1   2   3   4   5   6
    +---+---+---+---+---+---+---+
 0  |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+
 1  |   | A | B | C |   |   |   |
    +---+---+---+---+---+---+---+
 2  |   | D | E | F |   |   |   |
    +---+---+---+---+---+---+---+
 3  |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+

如果要将 6 个字母单元格作为子矩阵传递给函数，则需要传递包含 A 的单元格的地址，你需要知道有 3 列和 2 行，并且你还需要知道整个矩阵的宽度是 7。没有 7，你将无法找到单元格 D、E、F。这是你的缩小版当然是 1000x1000 阵列。

您的子矩阵位于整个矩阵的左上角，但适用相同的规则：您需要起始地址、子矩阵的宽度和高度以及完整矩阵的整体宽度才能访问正确的元素。

（顺便说一句，当我第一次开始解释时，上面的矩阵是 4x6，而不是 4x7。然后解释需要传递的 6 与 2x3 的乘积（子矩阵的大小）无关，所以很棘手，所以我更改了“测试用例”以避免出现问题 - 完全按照“选择良好的测试数据”下的建议。）

---

如何修复您的代码？

方法有很多，取决于你想做什么。困难的方法是传递重要的矩阵宽度参数。更简单的方法可能是分配一维单元格数组，然后手动计算下标。但是，我不确定你想要什么，给定输入值 14, 13, 12, 11 （相反顺序），输出矩阵应该是......什么？

12  11
14  13

这意味着您需要交换矩阵的整行。