在C语言中使用qsort对字符数组进行排序

Question

我正在尝试使用qsort对字符数组进行排序。但是我不知道为什么它不能正常工作。我已经按照man页面的说明，将比较函数的指针作为参数传递给了qsort。请问有人能告诉我问题出在哪里吗？谢谢。以下是我的代码：

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

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

void AlphabetSoup( char str[] ) {
  qsort(str, (size_t) strlen(str), (size_t) sizeof(char), cmpfunc);
  printf("%s\n", str);
}


int main() {
  char str1[] = "bcead";

  AlphabetSoup(str1);

  return 0;
}

输出结果为dabce，而我期望的是abcde。

- user1527227

Answer 1

简单错误。

在cmpfunc中使用char*而不是int*。

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

当你使用 int* 而不是 char* 时，指针变量 a 所指向的地址将被解释为一个 int 类型的地址，而不是一个 char 类型的地址。

你的输入包含以下字符：

+---+---+---+---+---+
| b | c | e | a | d |
+---+---+---+---+---+

十六进制表示如下：

+----+----+----+----+----+
| 62 | 63 | 65 | 61 | 64 |
+----+----+----+----+----+
^    ^
|    |
a    b

如果您将指向a和b的地址视为int*，假设您的系统中一个int占用4个字节，则*(int*)a可以是以下两种情况之一：

0X62*2^24 + 0X63*2^16 + 0X65*2^8 + 0X61

或者

0X62 + 0X63*2^8 + 0X65*2^16 + 0X61*2^24

根据您使用的是大端系统还是小端系统，*(int*)a 的值会有所不同。

类似地，您可以计算出 *(int*)b 的值。正如您所看到的，您已经遇到了意外的数字比较。当您开始比较输入中其他字节位置上的值时，您还使用了不应该使用的内存，并且进入了未定义行为的领域。

- R Sahu

Answer 2

你至少有两个问题。

首先，你试图对编译器可以存储在不可变内存中的静态定义文字内容进行排序。

其次，更重要的是，你将void*在比较函数中转换为int*。假设sizeof(int)==4，并且sizeof(char)==1，则你实际上正在将0-3号字符“作为整数”与1-4号字符“作为整数”进行比较。

在sizeof(int)=8（即64位编译器）的情况下，情况会更糟。将void*转换为char*类型，你应该没问题。

- caskey

---

str1被初始化为"bcead\0"，大小为6。它不在“不可变的RAM”中。关于int部分是正确的。 - chux - Reinstate Monica

Answer 3

问题出在比较函数comfunc中的类型转换操作符上。

int cmpfunc(const void *a, const void *b) {
  // error. casting to int * instead of char *
  return *(int*)a - *(int*)b; 
}

将空指针 a 转换为 int * 并进行反引用，意味着它将从 a 所包含地址的开始处读取 sizeof(int) 字节。因此，返回语句中的表达式是将来自 a 所在地址的 sizeof(int) 字节数与来自 b 所在地址的 sizeof(int) 字节数进行比较，而非比较指针 a 和 b 所包含地址中的字符。为了说明这一点，我将比较函数更改为

int cmpfunc(const void *a, const void *b) {
  printf("comparing %c and %c\n", *((char *)a), *((char *)b));
  printf("compare as int %d - %d = %d\n", *(int *)a, *(int *)b, *(int *)a - *(int *)b);
  printf("compare as char %d - %d = %d\n", *(char *)a, *(char *)b, *(char *)a - *(char *)b);
  return *(char *)a - *(char *)b;
}

这是我得到的输出。

comparing b and c
compare as int 1634034530 - 1684104547 = -50070017
compare as char 98 - 99 = -1
comparing a and d
compare as int 25697 - 100 = 25597
compare as char 97 - 100 = -3
comparing e and a
compare as int 6578533 - 25697 = 6552836

当将类型转换为int *和char *后进行比较时，读取的值之间存在差异。应更改比较函数为：

int cmpfunc(const void *a, const void *b) {
      // typecast the void pointers to correct type
      return *(char *)a - *(char *)b; 
}

此外，您不需要将 strlen 函数和 sizeof 运算符的结果转换为 size_t 类型，因为它们已经返回 size_t 类型的值。此外，使用数组元素上的 sizeof 更易读且更易于维护。您应该简单地调用 qsort。

qsort(str, strlen(str), sizeof str[0], cmpfunc);

- ajay

---

谢谢您提供解决方案，不仅仅是关于为什么的信息（当然这也很有帮助）。 - jthomas