如何使用原生 qsort 对 C 中的 `int **` 数组进行排序

Question

我一直找不到关于此的任何问题，我想我要弄清楚这个问题有点疯狂。

我有以下代码：

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

int cmp_int(const void *a, const void *b)
{
  return * (int *)a - * (int *)b;
}

int main(int argc, char *argv[])
{
  int n = 10;
  int **arr = calloc(n, sizeof(int *));
  srand((unsigned int) time(NULL));
  for (int i = n-1; i >= 0; i--) {
    arr[i] = calloc(1, sizeof(int));
    *(arr[i]) = rand() % 1000;
  }
  for (int i = 0; i < n; i++)
    printf("%d ", *(arr[i]));
  printf("\n");
  qsort(arr, 10, sizeof(void *), cmp_int);
  for (int i = 0; i < n; i++)
    printf("%d ", *(arr[i]));
  printf("\n");
  free(arr);
  return 0;
}

这是超级基本的，对吧？根据联机帮助页，第一个参数是指向基本元素的指针，第三个参数是大小。但是，我无法将数组作为排序结果。我仍然对 qsort 的第一个和第三个参数应该是什么感到困惑，因为我怀疑那是错误所在。

感谢任何帮助。

谢谢。

编辑：我应该补充一点，这段代码显然没有错误检查，而且我试图用一个双指针整数数组来测试 qsort，所以虽然是的，但我可以使用一个不是预期目的的常规数组这段代码的一部分（它实际上是一个单独程序中更大部分的一部分）。

Answer 1

你的程序让我很头疼。你没有得到正确排序的原因是比较函数是错误的。需要 return **(int **)a - **(int **)b; 才能得到正确的结果。

然而，以这种方式解决问题并不值得。至少列出了一些问题：

如果您不使用 argc 和 argv，请不要声明它们。
在 srand 调用中强制转换是不必要的。
int 通过减法进行比较是个坏主意，因为它会溢出。
calloc returns 应始终检查空（内存不足）结果。
calloc 根本不需要。使用变长数组。
无需分配指向整数的指针数组。只需分配一个整数数组。然后你的比较按原样工作。
qsort 调用使用硬常量 10 而不是 n。
通过取消引用数组名称来给出元素大小更不容易出错。
最后，您释放了 "spine" 数组，但没有释放整数元素。
你应该分解出一个函数来打印数组。

这是解决这些问题的版本。

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

int cmp_int(const void *va, const void *vb)
{
  int a = *(int *)va, b = *(int *) vb;
  return a < b ? -1 : a > b ? +1 : 0;
}

void print(int *a, int n) {
  for (int i = 0; i < n; ++i) printf("%d ", a[i]);
  printf("\n");
}

int main(void)
{
  int n = 10, a[n];
  srand(time(0));
  for (int i = 0; i < n; ++i) a[i] = rand() % 1000;
  print(a, n);
  qsort(a, n, sizeof a[0], cmp_int);
  print(a, n);
  return 0;
}

Answer 2

您遇到的问题是未能考虑通过使用 int **arr = calloc (n, sizeof *arr); 分配一个指针块然后为每个指针分配单个 int 的存储而创建的一个额外的间接级别arr[i] = calloc (1, sizeof *arr[i]).

由于 qsort 的 int compare (const void *a, const void *b) 比较函数需要 指向正在排序的数组元素的指针 ，因此 a 和 b 上面的 pointer-to-pointer 到 int 在你的情况下需要在比较整数值之前取消引用 2 个间接级别。

而不是 cmp_int，您实际上需要一个 cmp_int_ptr 比较函数。可以写成：

int cmp_int_ptr (const void *a, const void *b)
{
    int *ai = *(int * const *)a,
        *bi = *(int * const *)b;

    return (*ai > *bi) - (*ai < *bi);
}

(注： cast中的两层间接寻址(int * const *)...也可以写成(int **)，但是要对应参数类型 (const void *) (int * const *) 正确）

将其放置到位，为每个分配添加验证并通过使用解除引用的指针本身设置类型大小来清理 calloc 类型大小规范，您可以执行以下操作：

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

int cmp_int_ptr (const void *a, const void *b)
{
    int *ai = *(int * const *)a,
        *bi = *(int * const *)b;

    return (*ai > *bi) - (*ai < *bi);
}

int main (void) {

    int n = 10;
    int **arr = calloc (n, sizeof *arr);

    if (!arr) {
        perror ("calloc-arr");
        return 1;
    }

    srand((unsigned int) time(NULL));

    for (int i = 0; i < n; i++) {
        if (!(arr[i] = calloc (1, sizeof *arr[i]))) {
            perror ("calloc-arr[i]");
            return 1;
        }
        *(arr[i]) = rand() % 1000;
    }

    for (int i = 0; i < n; i++)
        printf (" %d", *(arr[i]));
    putchar ('\n');

    qsort (arr, 10, sizeof *arr, cmp_int_ptr);

    for (int i = 0; i < n; i++) {
        printf (" %d", *(arr[i]));
        free (arr[i]);              /* don't forget to free your int allocated */
    }
    putchar ('\n');

    free(arr);                      /* now free pointers */
}

例子Use/Output

$ ./bin/qsortptrtoint
 654 99 402 264 680 534 155 533 397 678
 99 155 264 397 402 533 534 654 678 680

检查一下，如果您有任何问题，请告诉我。

如何使用原生 qsort 对 C 中的 `int **` 数组进行排序

How to sort an `int **` array in C with native qsort

c

sorting

qsort