C - 按一维排序二维数组

Question

我有一个二维数组，我试图按升序排序。例如，假设数组是这样的：

4, 5 
2, 6 
7, 2 
8, 4 

我想它看起来就像这样：

2, 6 
4, 5 
7, 2 
8, 4 

是我到目前为止的代码：

int temp = 0; 
for(int m = 0; m<=nonZeroLength-1; m++){ 
    for(int n = m+1; n<=nonZeroLength-1; n++){ 
     if(nonZeroScoreSorcting[m] > nonZeroScoreSorcting[m+1]){ 
      temp = nonZeroScoreSorcting[m]; 
      strcpy(nonZeroScoreSorcting[m], nonZeroScoreSorcting[n]); 
      strcpy(nonZeroScoreSorcting[n], temp); 
     } 
    } 
} 

假设本例中nonZeroLength的值为4。我使用strcpy()，因为我读到那就是更改数组的元素下的唯一途径。当我运行程序时出现错误（不知道如果多数民众赞成真正虽然）：

passing argument 1 of ‘strcpy’ from incompatible pointer type [-Wincompatible-pointer-types]

我有也尝试了常规的分配方法：

if(nonZeroScoreSorcting[m] > nonZeroScoreSorcting[m+1]){ 
    temp = nonZeroScoreSorcting[m]; 
    nonZeroScoreSorcting[m] = nonZeroScoreSorcting[n]; 
    nonZeroScoreSorcting[n] = temp; 
} 

Answer 1

如果事实上确实有int一个二维数组，你指出，关键要排序按行阵列的理解是，排序过程中，您将需要交换行，而不仅仅是值。这就是你在排序过程中如何保持行方面的关系。

你不能这样做，治疗的int每一行作为一个字符串和使用strcpy尝试，在行副本。这将导致未定义的行为当strcpy访问src参数中的值在数组范围外寻找最终字符不存在。

（虽然在技术上，提供适当大小的阵列每个src和dest和上浆在strncpy'n'复制2 * sizeof(int)字节可以借助于复制读限制n字符的行，其中没有NUL终止字符是目前 - 但不要这样做 - 这就是memcpy（或memmove））。

尽管在C中推荐的排序方式是使用stdlib.h中提供的qsort函数，但您可以提供您想要的任何排序算法。它可能不会接近qsort的效率，当然也不会经过彻底测试。一个简单的行排序使用慢速旧插入排序可以做如下：

#include <stdio.h> 
#include <string.h> 

int main (void) { 

    int a[][2] = {{ 4, 5 }, 
        { 2, 6 }, 
        { 7, 2 }, 
        { 8, 4 }}, 
     n = sizeof a/sizeof *a, 
     col = sizeof *a/sizeof **a; 

    for (int i = 0; i < n; i++) /* insertion sort of a by row */ 
     for (int j = i; j > 0 && *a[j] < *a[j-1]; j--) { 
      int tmp[col]; /* temporary VLA */ 
      memcpy (tmp, a[j], sizeof *a); 
      memcpy (a[j], a[j-1], sizeof *a); 
      memcpy (a[j-1], tmp, sizeof *a); 
     } 

    for (int (*p)[2] = a; p < a + n; p++) /* output results */ 
     printf ("%d, %d\n", (*p)[0], (*p)[1]); 

    return 0; 
} 

示例使用/输出

$ ./bin/inssort2d 
2, 6 
4, 5 
7, 2 
8, 4 

随着qsort大多数新的C程序员具有写一个被难倒比较函数传递给qsort让它做它的工作。这实际上并不那么困难。你知道qsort会传递指向你比较函数参数的两个指针。

在这种情况下，您将基于每行的第一个元素排序整数行（1D整数数组）。所以qsort会比较两个int *（指向int的指针）。你只关心每个数组中的第一个元素（你可以简单地通过解引用指针来获得）。一个比较这里可以是一个简单：

int cmp (const void *a, const void *b) 
{ 
    /* (a > b) - (a < b) */ 
    return (*(int *)a > *(int *)b) - (*(int *)a < *(int *)b); 
} 

（注：使用两个不等式你防止溢出/下溢，如果你只是独自返回减法的结果可能发生的结果）。

完整qsort实现是：

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

int cmp (const void *a, const void *b) 
{ 
    /* (a > b) - (a < b) */ 
    return (*(int *)a > *(int *)b) - (*(int *)a < *(int *)b); 
} 

int main (void) { 

    int a[][2] = {{ 4, 5 }, 
        { 2, 6 }, 
        { 7, 2 }, 
        { 8, 4 }}, 
     n = sizeof a/sizeof *a; 

    qsort (a, n, sizeof *a, cmp); /* qsort array of pointers */ 

    for (int (*p)[2] = a; p < a + n; p++) /* output results */ 
     printf ("%d, %d\n", (*p)[0], (*p)[1]); 

    return 0; 
} 

（输出是一样的）

查看这两种方法，知道qsort是首选的方法，但对于学习，有什么错亲自动手获取经验。如果您还有其他问题，请告诉我。