c - C 中的二维数组排序

Question

我正在为 C 语言类(class)开发一个项目。

• 我需要对六个整数的数组进行排序:{a,b,c,n,m,v}。
• 我需要按照n的值升序对它进行排序，如果它有两个或多个具有相同n的数组，我需要按照m的升序对它进行排序。

我根据冒泡排序算法编写了这段代码，但如果我尝试对许多数组进行排序，它就不起作用:

void bubbleSort(int arraySize)
{
    int tempEntry[6];
    for (int i = 0; i < arraySize - 1; i++) //Loop for ascending ordering
    {
        for (int j = 0; j < arraySize - 1 - i; j++) //Loop for comparing other values
        {
            if (sortedArray[j][3] > sortedArray[j + 1][3]) //Comparing other array elements . n1>n2
            {
                copyTripleToArray(sortedArray[j], 0, 2, tempEntry); //Using temporary variable for storing last value
                copyTripleToArray(sortedArray[j + 1], j, 0, NULL); //replacing value
                copyTripleToArray(tempEntry, j + 1, 0, NULL);  //storing last value
            }
            if (sortedArray[j][3] == sortedArray[j + 1][3] && sortedArray[j][4] > sortedArray[j + 1][4]) //Comparing other array elements. n1=n2, m1>m2
            {
                copyTripleToArray(sortedArray[j], 0, 2, tempEntry); //Using temporary variable for storing last value
                copyTripleToArray(sortedArray[j + 1], j, 0, NULL); //replacing value
                copyTripleToArray(tempEntry, j + 1, 0, NULL);  //storing last value
            }
        }
    }
}

copyTripleToArray() 的说明:

The function copies the triple into the suitable index in sortedArray (buffer = 0), or in outputBuffer (buffer = 1) or in tempArray (buffer = 2).

void copyTripleToArray(int PrimitivePythagoreanTriple[], int index, int buffer, int tempArray[])
{
    if (buffer == 1) //the array is outputBuffer
    {
        for (int i = 0; i < NUM_OF_ELENENTS_IN_ARRAY; i++) //first case: loop to copy all the entries
            outputBuffer[index][i] = PrimitivePythagoreanTriple[i]; // copy the array to buffer.
        return;
    }
    else if (buffer == 0) //the array is outputBuffer
    {
        for (int i = 0; i < NUM_OF_ELENENTS_IN_ARRAY; i++) //secound case: loop to copy all the entries into sortedArray
            sortedArray[index][i] = PrimitivePythagoreanTriple[i]; // copy the array to sortedArray.
        return;
    }
    for (int i = 0; i < NUM_OF_ELENENTS_IN_ARRAY; i++) //third case: loop to copy all the entries into tempArray
        tempArray[i] = PrimitivePythagoreanTriple[i]; // copy the array to tempArray.
}

sortedArray 是要排序的数组；它是一个全局数组。

copyTripleToArray 将整数数组复制到 sortedArray 中的特定索引或临时数组。

我做错了什么？

Answer 1

很难解决这个问题，因为它缺乏 MCVE 的品质( Minimal, Complete, Verifiable Example )。对要排序的数组使用全局变量是一个坏主意；将数组传递给排序函数。

你说:

… it doesn't work if I try to sort many arrays

你应该解释一下它在什么方面不起作用。一个明显的问题是，您必须将数据复制到全局数组中才能对每组数据进行排序。这是您应该将数组传递给排序函数而不是依赖全局变量的众多原因之一。谨慎对待全局变量。仅当替代方案(作为参数传递)太痛苦时才使用它们(“痛苦”是导致您使用全局变量的最小程度的痛苦；不要仅仅因为“不舒服”甚至只是“痛苦”而推迟)。

琐事:“Elements”中有一个 m - 你的巨大的长 NUM_OF_ELENENTS_IN_ARRAY 没有在正确的位置有一个 M。然而，变量和常量的名称太长了，让我感到不舒服。是的;选择有意义的名字是件好事。不;没有必要在名字中写入语法正确的文章。我使用了NUM_VALUES； NUM_COLUMNS 也可以。它们足够长且有意义。

更严重的是，你有一个没有解释的全局变量OutputBuffer——它在copyTripleToArray()中被引用，对于一个函数来说这是一个奇怪的名字复制 6 个元素。然而，仔细观察发现，它仅在 buffer == 1 时使用，但您永远不会使用 buffer == 1 调用该函数，因此可以删除该代码块(已注释掉)。

你的copyTripleToArray()函数有点奇怪。您应该简单地提供一个指向要复制出的行和要复制到的行的指针，然后让它继续复制。您需要这么多参数，这很奇怪。两个或三个就足够了(取决于您是否将 NUM_VALUES 传递给函数)。

问题代码的轻微修改版本

但是，当一切都说了又做了之后，代码似乎可以工作。至少，我在下面的代码中所做的修改应该是微不足道的。我创建并填充了一个数组，并在其上运行代码，它似乎产生了正确的结果。

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

enum { NUM_VALUES = 6 };
enum { NUM_OF_ELEMENTS_IN_ARRAY = NUM_VALUES };

static int sortedArray[][NUM_VALUES];   // Forward declaration

static void copyTripleToArray(int PrimitivePythagoreanTriple[], int index, int buffer, int tempArray[])
{
    //if (buffer == 1)
    //{
        //for (int i = 0; i < NUM_OF_ELEMENTS_IN_ARRAY; i++)
            //outputBuffer[index][i] = PrimitivePythagoreanTriple[i];
    //}
    //else if (buffer == 0)
    if (buffer == 0)
    {
        for (int i = 0; i < NUM_OF_ELEMENTS_IN_ARRAY; i++)
            sortedArray[index][i] = PrimitivePythagoreanTriple[i];
    }
    else
    {
        for (int i = 0; i < NUM_OF_ELEMENTS_IN_ARRAY; i++)
            tempArray[i] = PrimitivePythagoreanTriple[i];
    }
}

static void bubbleSort(int arraySize)
{
    int tempEntry[NUM_VALUES];
    for (int i = 0; i < arraySize - 1; i++)
    {
        for (int j = 0; j < arraySize - 1 - i; j++)
        {
            if (sortedArray[j][3] > sortedArray[j + 1][3])
            {
                copyTripleToArray(sortedArray[j], 0, 2, tempEntry);
                copyTripleToArray(sortedArray[j + 1], j, 0, NULL);
                copyTripleToArray(tempEntry, j + 1, 0, NULL);
            }
            if (sortedArray[j][3] == sortedArray[j + 1][3] &&
                sortedArray[j][4] >  sortedArray[j + 1][4])
            {
                copyTripleToArray(sortedArray[j], 0, 2, tempEntry);
                copyTripleToArray(sortedArray[j + 1], j, 0, NULL);
                copyTripleToArray(tempEntry, j + 1, 0, NULL);
            }
        }
    }
}

static void print_array(const char *tag, size_t size, int data[size][NUM_VALUES])
{
    printf("%s (%zux%d):\n", tag, size, NUM_VALUES);
    for (size_t i = 0; i < size; i++)
    {
        printf("%3zu:", i);
        for (int j = 0; j < NUM_VALUES; j++)
            printf(" %3d", data[i][j]);
        putchar('\n');
    }
}

static int sortedArray[][NUM_VALUES] =
{
    // random -n 30 -T '%d %d %d %d %d %d' 10 29 |
    // commalist -n 6 -B 4 -b '{ ' -w -W 3 -T ' },'
    {  25,  18,  29,  25,  12,  18, },
    {  29,  29,  24,  23,  26,  28, },
    {  16,  22,  10,  15,  23,  29, },
    {  27,  22,  16,  27,  19,  24, },
    {  17,  18,  10,  20,  15,  24, },
    {  21,  11,  19,  15,  13,  15, },
    {  16,  11,  19,  13,  10,  25, },
    {  17,  17,  15,  27,  26,  24, },
    {  12,  23,  24,  28,  24,  15, },
    {  11,  21,  25,  15,  18,  25, },
    {  12,  14,  25,  11,  13,  29, },
    {  16,  12,  11,  21,  19,  28, },
    {  18,  16,  20,  17,  15,  11, },
    {  13,  18,  11,  23,  23,  18, },
    {  29,  16,  29,  10,  22,  28, },
    {  13,  15,  24,  24,  28,  26, },
    {  28,  26,  13,  27,  18,  27, },
    {  10,  29,  18,  15,  24,  29, },
    {  24,  24,  27,  24,  21,  12, },
    {  10,  28,  12,  11,  27,  25, },
    {  12,  21,  28,  27,  11,  14, },
    {  19,  17,  11,  18,  25,  23, },
    {  19,  21,  10,  21,  20,  22, },
    {  18,  29,  12,  15,  28,  22, },
    {  25,  16,  15,  23,  27,  21, },
    {  28,  16,  11,  10,  24,  23, },
    {  29,  19,  22,  20,  28,  27, },
    {  16,  21,  17,  16,  25,  15, },
    {  11,  23,  17,  19,  27,  13, },
    {  12,  15,  18,  16,  26,  14, },
};

enum { NUM_ROWS = sizeof(sortedArray) / sizeof(sortedArray[0]) };

int main(void)
{
    print_array("Before", NUM_ROWS, sortedArray);
    bubbleSort(NUM_ROWS);
    print_array("After", NUM_ROWS, sortedArray);
    return 0;
}

示例运行:

Before (30x6):
  0:  25  18  29  25  12  18
  1:  29  29  24  23  26  28
  2:  16  22  10  15  23  29
  3:  27  22  16  27  19  24
  4:  17  18  10  20  15  24
  5:  21  11  19  15  13  15
  6:  16  11  19  13  10  25
  7:  17  17  15  27  26  24
  8:  12  23  24  28  24  15
  9:  11  21  25  15  18  25
 10:  12  14  25  11  13  29
 11:  16  12  11  21  19  28
 12:  18  16  20  17  15  11
 13:  13  18  11  23  23  18
 14:  29  16  29  10  22  28
 15:  13  15  24  24  28  26
 16:  28  26  13  27  18  27
 17:  10  29  18  15  24  29
 18:  24  24  27  24  21  12
 19:  10  28  12  11  27  25
 20:  12  21  28  27  11  14
 21:  19  17  11  18  25  23
 22:  19  21  10  21  20  22
 23:  18  29  12  15  28  22
 24:  25  16  15  23  27  21
 25:  28  16  11  10  24  23
 26:  29  19  22  20  28  27
 27:  16  21  17  16  25  15
 28:  11  23  17  19  27  13
 29:  12  15  18  16  26  14
After (30x6):
  0:  29  16  29  10  22  28
  1:  28  16  11  10  24  23
  2:  12  14  25  11  13  29
  3:  10  28  12  11  27  25
  4:  16  11  19  13  10  25
  5:  21  11  19  15  13  15
  6:  11  21  25  15  18  25
  7:  16  22  10  15  23  29
  8:  10  29  18  15  24  29
  9:  18  29  12  15  28  22
 10:  16  21  17  16  25  15
 11:  12  15  18  16  26  14
 12:  18  16  20  17  15  11
 13:  19  17  11  18  25  23
 14:  11  23  17  19  27  13
 15:  17  18  10  20  15  24
 16:  29  19  22  20  28  27
 17:  16  12  11  21  19  28
 18:  19  21  10  21  20  22
 19:  13  18  11  23  23  18
 20:  29  29  24  23  26  28
 21:  25  16  15  23  27  21
 22:  24  24  27  24  21  12
 23:  13  15  24  24  28  26
 24:  25  18  29  25  12  18
 25:  12  21  28  27  11  14
 26:  28  26  13  27  18  27
 27:  27  22  16  27  19  24
 28:  17  17  15  27  26  24
 29:  12  23  24  28  24  15

所以，我不清楚你的问题是什么。

修改后的代码

这是代码的简化版本，使用更简单的 copy_row() 函数，如果需要，可以升级为使用 memmove() 或 memcpy( ) 而不是在主体中有一个循环。

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

enum { NUM_VALUES = 6 };

static int sortedArray[][NUM_VALUES];    // Forward declaration

static void copy_row(int source[NUM_VALUES], int target[NUM_VALUES])
{
    for (int i = 0; i < NUM_VALUES; i++)
        target[i] = source[i];
}

static void bubbleSort(int arraySize)
{
    int tempEntry[6];
    for (int i = 0; i < arraySize - 1; i++)
    {
        for (int j = 0; j < arraySize - 1 - i; j++)
        {
            if ((sortedArray[j][3] > sortedArray[j + 1][3]) ||
                (sortedArray[j][3] == sortedArray[j + 1][3] &&
                 sortedArray[j][4] >  sortedArray[j + 1][4]))
            {
                copy_row(sortedArray[j], tempEntry);
                copy_row(sortedArray[j+1], sortedArray[j]);
                copy_row(tempEntry, sortedArray[j+1]);
            }
        }
    }
}

static void print_array(const char *tag, size_t size, int data[size][NUM_VALUES])
{
    printf("%s (%zux%d):\n", tag, size, NUM_VALUES);
    for (size_t i = 0; i < size; i++)
    {
        printf("%3zu:", i);
        for (int j = 0; j < NUM_VALUES; j++)
            printf(" %3d", data[i][j]);
        putchar('\n');
    }
}

static int sortedArray[][NUM_VALUES] =
{
    // random -n 30 -T '%d %d %d %d %d %d' 10 29 |
    // commalist -n 6 -B 4 -b '{ ' -w -W 3 -T ' },'
    {  25,  18,  29,  25,  12,  18, },
    {  29,  29,  24,  23,  26,  28, },
    {  16,  22,  10,  15,  23,  29, },
    {  27,  22,  16,  27,  19,  24, },
    {  17,  18,  10,  20,  15,  24, },
    {  21,  11,  19,  15,  13,  15, },
    {  16,  11,  19,  13,  10,  25, },
    {  17,  17,  15,  27,  26,  24, },
    {  12,  23,  24,  28,  24,  15, },
    {  11,  21,  25,  15,  18,  25, },
    {  12,  14,  25,  11,  13,  29, },
    {  16,  12,  11,  21,  19,  28, },
    {  18,  16,  20,  17,  15,  11, },
    {  13,  18,  11,  23,  23,  18, },
    {  29,  16,  29,  10,  22,  28, },
    {  13,  15,  24,  24,  28,  26, },
    {  28,  26,  13,  27,  18,  27, },
    {  10,  29,  18,  15,  24,  29, },
    {  24,  24,  27,  24,  21,  12, },
    {  10,  28,  12,  11,  27,  25, },
    {  12,  21,  28,  27,  11,  14, },
    {  19,  17,  11,  18,  25,  23, },
    {  19,  21,  10,  21,  20,  22, },
    {  18,  29,  12,  15,  28,  22, },
    {  25,  16,  15,  23,  27,  21, },
    {  28,  16,  11,  10,  24,  23, },
    {  29,  19,  22,  20,  28,  27, },
    {  16,  21,  17,  16,  25,  15, },
    {  11,  23,  17,  19,  27,  13, },
    {  12,  15,  18,  16,  26,  14, },
};

enum { NUM_ROWS = sizeof(sortedArray) / sizeof(sortedArray[0]) };

int main(void)
{
    print_array("Before", NUM_ROWS, sortedArray);
    bubbleSort(NUM_ROWS);
    print_array("After", NUM_ROWS, sortedArray);
    return 0;
}

使用相同的输入数据(和打印代码等)，它会产生相同的答案。我还没有正式验证保护属性 - 未排序数据中存在的所有行都存在于排序数据中。

进一步修改这段代码并不难，以便将要排序的数组作为参数而不是作为文件范围变量传递给排序函数。这是一个更强大、更容易重用的代码版本。

您可以在我的 SOQ 中找到代码(Stack Overflow Questions) GitHub 上的存储库为文件 sort31.c(问题中的代码)、sort67.c(将数组作为参数传递给排序)和 sort89 src/so-5380-3837 中的 .c (上面的代码)子目录。