矩阵排序归并排序 C

Question

我遇到了这个问题，我必须像这样对矩阵进行排序：

至：

所以行保持不变，每列从小到大，如示例所示。矩阵总是有 3 列和 x 行。

我已经尝试过插入排序，但尽管如此，它效率不高，并且考虑到实际应用程序中的行数，运行需要花费很多时间。

我将提供一个我假装的小代码：

#include <stdio.h>

int main() {
    int abc[6][3] = {
        { 0, 0, 4 },
        { 1, 0, 3 },
        { 0, 1, 4 },
        { 1, 1, 5 },
        { 0, 2, 3 },
        { 1, 2, 4 },
    };

    //
    //sort 
    //

    for (int i = 0; i < 6; ++i) {
        printf("%d %d %d\n", abc[i][0], abc[i][1], abc[i][2]);
    }
    return 0;
}

我想同时尝试合并排序和快速排序，但如有任何帮助，我们将不胜感激。

提前谢谢你。

Answer 1

您可以通过四种方式之一来编写您的比较函数（两种方式在形式上是正确的，但都是等价的 ¹）。可怕的 qsort 原型 int compare (const void *a, const void *b) 只是 C 将指针传递给要排序的数组元素的方式。您的工作只是在函数中比较之前转换回正确的类型。

真正的问题是“正在传递什么类型的指针？

当您回答时，这很容易。您正在按行对二维数组进行排序。二维数组实际上是一维数组的数组。传递给比较的每个指针都是指向一维数组（行）的指针

所以每个 a 和 b 将是 指向 int [3] 数组 的指针。在您的比较函数中，您需要转换为指向 int [3] 数组的指针，然后取消引用一次以将类型保留为 int [3]，然后根据第三个元素进行比较。（但是当您访问现在类型 int [3] 数组指针转换也适用于该数组时，因此您只需将 2 添加到您的指针值并取消引用以通过第三个元素进行比较）。

您可以使用两个条件测试的结果来避免简单地 returning b - a 可能导致的潜在溢出，如果 b 是一个大的负数并且 a 很大（或者 b 是一个大的正数，a 是一个大的负数），如果结果超过 int 的存储容量，将会发生。因此，对于升序排序，您可以使用：

    return (a > b) - (a < b);

（对于降序排序，只需翻转比较，例如 (a < b) - (a > b)。试试看。选择 a 和 b 的任意两个值并计算结果。在升序是 a 小于 b，你 return 0 - 1;（或 -1），例如意思是 a 在 b 之前排序）

那么比较函数是什么样的呢？由于 指向 int [3] 的数组 的指针的正式类型是 int (*)[3]，您可以这样做：

int comp (const void *a, const void *b)
{
    int *pa2 = *(int (*)[3])a + 2,
        *pb2 = *(int (*)[3])b + 2;

    return (*pa2 > *pb2) - (*pa2 < *pb2);
}

或者，如果您只想创建 int pa2 而不必担心必须在比较中取消引用指针，对于第二次正式转换，您可以将 a 的完整转换括在括号中，并且然后只需使用 (stuff a)[2] 直接访问第三个整数值——它只会让演员看起来更乱，例如

int comp (const void *a, const void *b)
{
    int pa2 = (*(int (*)[3])a)[2],
        pb2 = (*(int (*)[3])b)[2];

    return (pa2 > pb2) - (pa2 < pb2);
}

（您认为最有意义的）

那么按二维数组中每一行的第三个元素排序就很简单了，例如

#include <stdio.h>
#include <stdlib.h>

int comp (const void *a, const void *b)
{
    int *pa2 = *(int (*)[3])a + 2,
        *pb2 = *(int (*)[3])b + 2;

    return (*pa2 > *pb2) - (*pa2 < *pb2);
}

int main() {

    int abc[6][3] ={{0,0,4},
                    {1,0,3},
                    {0,1,4},
                    {1,1,5},
                    {0,2,3},
                    {1,2,4}};

    qsort (abc, 6, sizeof *abc, comp);

    for (int i = 0; i < 6; ++i)
        printf(" %2d %2d %2d\n", abc[i][0], abc[i][1], abc[i][2]);

}

例子Use/Output

$ ./bin/qsort2d+2
  1  0  3
  0  2  3
  0  0  4
  0  1  4
  1  2  4
  1  1  5

现在，写比较函数强制转换的最后两种等效方法依赖于连续应用 array/pointer 转换并理解指向数组的指针和数组本身都将指向相同的地址（但是正式的不同类型）正式你有 int (*)[3] 但因为你知道你只想要该地址后的第二个整数，你可以将比较指针 a 和 b 转换为 int *并添加两个。这是等效的，但不反映正式的转换。（您也可以将整个演员表括在括号中并使用 [2]）。

在那种情况下，转换看起来要简单得多，但实际上发生的事情可能不太明显。我将留给您尝试将完整程序中的 *(int (*)[3]) 替换为 (int *)。（这将避免在评论中进行长时间的讨论）

仔细想想 "What type pointer is being passed?" 以及为什么在比较中使用两次比较的结果而不只是减法作为 return避免溢出的功能。如果您还有其他问题，请告诉我。

脚注：

1.) C11 Standard - 6.3.2.1 Other Operands - Lvalues, arrays, and function designators(p3) 除非它是 sizeof 运算符、_Alignof 运算符或一元 '&' 运算符，或者是用于初始化数组的 字符串文字 ，类型为 "array of type" 的表达式将转换为类型为 "pointer to type" 的表达式，它指向数组对象的初始元素并且不是左值。

Answer 2

基于 David C. Rankin 的回答，您还必须考虑另一个问题：您希望获得的精确排序顺序是什么？

从你提供的例子可以推断，二维数组的第三列是主键。然而，这不足以完全指定排序顺序。以下是三种可能性：

第三列中具有相同元素的行的顺序无关紧要。在这种情况下，可能有很多不同的输出，都是正确的。
具有相同元素的行的顺序应与原始二维数组中的顺序相同。为此，您需要一个稳定的排序算法，例如 mergesort，但是 qsort 通常混合使用快速排序和其他用于病态情况的方法来实现，使其不稳定，因此不适合您的目的.
第 3 列中具有相同元素的行的顺序应根据第二列中的值确定，如果这些值也相同，则应根据第一列中的值确定。提供的示例与此方法一致。（根据您对 Jonathan Leffler 评论的回复，这应该是您的偏好）。

qsort()适用于方法1和3，但不适用于方法2。

下面是方法 1 的比较简单的比较函数：

int comp2(const void *a, const void *b) {
    const int *pa = a;
    const int *pb = b;

    return (pa[2] > pb[2]) - (pa[2] < pb[2]);
}

comp2 可用于方法 2，但必须调用 mergesort() 而不是 qsort():

mergesort(abc, sizeof abc / sizeof *abc, sizeof *abc, comp2);

这里是方法 3 的比较函数：

int comp_full(const void *a, const void *b) {
    const int *pa = a;
    const int *pb = b;

    if (pa[2] != pb[2])
        return (pa[2] > pb[2]) - (pa[2] < pb[2]);
    if (pa[1] != pb[1])
        return (pa[1] > pb[1]) - (pa[1] < pb[1]);
    else
        return (pa[0] > pb[0]) - (pa[0] < pb[0]);
}

这里是BSD系统的测试程序：

#include <stdio.h>
#include <stdlib.h>

int comp_full(const void *a, const void *b) {
    const int *pa = a;
    const int *pb = b;

    if (pa[2] != pb[2])
        return (pa[2] > pb[2]) - (pa[2] < pb[2]);
    if (pa[1] != pb[1])
        return (pa[1] > pb[1]) - (pa[1] < pb[1]);
    else
        return (pa[0] > pb[0]) - (pa[0] < pb[0]);
}

int comp2(const void *a, const void *b) {
    const int *pa = a;
    const int *pb = b;

    return (pa[2] > pb[2]) - (pa[2] < pb[2]);
}

int use_stable_sort = 0;

int main() {
    int abc[][3] = {
        { 0, 0, 4 },
        { 1, 0, 3 },
        { 0, 1, 4 },
        { 1, 1, 5 },
        { 0, 2, 3 },
        { 1, 2, 4 },
    };

    if (use_stable_sort)
        mergesort(abc, sizeof abc / sizeof *abc, sizeof *abc, comp2);
    else
        qsort(abc, sizeof abc / sizeof *abc, sizeof *abc, comp_full);

    for (int i = 0, n = sizeof abc / sizeof *abc; i < n; ++i)
        printf("%d %d %d\n", abc[i][0], abc[i][1], abc[i][2]);

    return 0;
}

矩阵排序归并排序 C

Matrix Sorting mergesort C

c

sorting

mergesort

quicksort