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是首選的方法，但對於學習，有什麼錯親自動手獲取經驗。如果您還有其他問題，請告訴我。