在C语言中按字母顺序排序单词

Question

以下代码是为了一个测试样例而给出的https://www.testdome.com/for-developers/solve-question/9621。

问题是： 实现函数sort_words，可以对包含英语字母小写字符的单词数组进行降序排序。

例如，数组{"cherry", "orange", "apple"}在排序后应变为{"orange", "cherry", "apple"}。

我的代码是：

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

void sort_words(char *words[], int count)
{
    char *x;

    for (int i = 0; i<count; i++)
    {
        for (int j = i + 1; j<count; j++)
        {
            if ((char)(*words[i]) < (char)(*words[j]))
            {
                x = words[j];
                words[j] = words[i];
                words[i] = x;
            }
        }

    }
}

#ifndef RunTests
int main()
{
    char *words[] = { "cherry", "orange", "apple" };

    sort_words(words, 3);

    for (int i = 0; i < 3; i++)
    {
        printf("%s ", words[i]);
    }
}
#endif

结果是正确的，但系统提示失败信息：“在字典上进行性能测试：超时限制”

为什么会出现这个错误，如何解决这个问题？谢谢！

- Sunny Lei

---

你只比较字符串的首字母，这在你的最小样本数据中足够了，但通常并不足够。你不能保证把 apple、apricot、artichoke、alfafa 按正确顺序排序。你的排序算法是二次方的 O（N ^ 2），而不是 O（N.logN）。这可能就是问题所在。如果字典中有 10,000 个单词，那么这大约相当于 1E8 和 1.5E5 的差异，即约为 125 倍的因数差异。 - Jonathan Leffler

你将这些表达式强制转换为 char，这表明你不确定 *words[i] 到底是什么。 - WhozCraig

使用qsort函数。例如： int cmp(const void *a, const void *b){ return strcmp(*(char**)b, *(char**)a); } void sort_words(char *words[], int count) { qsort(words, count, sizeof(*words), cmp); } - BLUEPIXY

@BLUEPIXY qsort()很好用，strcmp()可以直接使用，在这种情况下不需要cmp()函数。 - Bjorn A.

@BjornA。由于qsort的compare函数接收char **，因此无法直接使用。您的提案得出了错误的结果，而我的提案得出了正确的结果。 - BLUEPIXY

Answer 1

这是因为你使用的算法在时间复杂度方面不够高效。你所使用的算法非常简单。它无疑可以对输入进行排序，但当输入数据集很大时，会耗费大量时间。尝试使用其他排序算法，如-归并排序，快速排序等。这些算法将在更短的时间内完成相同的工作。 参考这些算法的工作原理，并尝试实现它们-https://www.tutorialspoint.com/data_structures_algorithms/sorting_algorithms.htm

- Rajeev Ranjan

Answer 2

以上代码看起来可以运行，但实际上是错误的。

如果输入集是： char *words[] = { "cherry", "orange", "apple", "oyster"}; 那么输出结果应该是：

orange oyster cherry apple

但期望的输出结果是：

oyster orange cherry apple

那是因为你的排序算法中有这个条件：
if ((char)(*words[i]) < (char)(*words[j]))
基本上只是比较两个字符数组的第一个字母。
注意：这不是C++，数据没有在C++的string数据类型中存储，而<运算符被重载用于比较两个字符串。
因此，你可以使用strcmp()代替那一行，写成以下形式：

if (strcmp(words[i], words[j]) < 0)

这是您的可用代码：

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

void sort_words(char *words[], int count)
{
    char *x;

    for (int i = 0; i<count; i++)
    {
        for (int j = i + 1; j<count; j++)
        {
            if (strcmp(words[i], words[j]) < 0)
            {
                x = words[j];
                words[j] = words[i];
                words[i] = x;
            }
        }

    }
}

#ifndef RunTests
int main()
{
    char *words[] = { "cherry", "orange", "apple", "oyester"};

    sort_words(words, 4);

    for (int i = 0; i < 4; i++)
    {
        printf("%s ", words[i]);
    }
    printf ("\n");
}
#endif

输出：

oyester orange cherry apple

- NVS Abhilash

Answer 3

你可以使用C标准库函数qsort()来解决这个问题......下面是我的代码：

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int compare_c_str(const void * str1, const void * str2)
{

    return strcmp(*(char **)str2,*(char **)str1);
}

void sort_words(char *words[], int count)
{
    // Waiting to be implemented
    qsort(words,count, sizeof(words[0]),compare_c_str);
}

#ifndef RunTests
int main()
{
    char *words[] = { "cherry", "orange", "apple" };

    sort_words(words, 3);

    for (int i = 0; i < 3; i++)
    {
        printf("%s ", words[i]);
    }
}
#endif

- xubo peng

---

它通过了所有的测试。 - xubo peng