如何按字母表顺序对字符串数组进行排序（区分大小写，使用非标准排序）

Question

我需要一段C语言代码来排序一些字符串，它应该是区分大小写的，并且对于相同的大写和小写字母，应该先出现小写字母。例如，对于以下字符串进行排序的结果：

eggs
bacon
cheese
Milk
spinach
potatoes
milk
spaghetti

应该是：

bacon
cheese
eggs
milk
Milk
potatoes
spaghetti
spinach

我写了一段代码，但我得到的结果是：

Milk
bacon
cheese
eggs
milk
potatoes
spaghetti
spinach

我不知道如何改进这个问题，我已经搜索了很多。 有人能帮助我吗？

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

int main(){
    char c;
    char name[20][10], temp[10];
    int count_name = 0;
    int name_index = 0;
    int i, j;

    while ((c = getchar()) != EOF){
        if (c == 10){
            name[count_name][name_index] = '\0';
            count_name++;
            name_index = 0;
        } else {
            name[count_name][name_index] = c;
            name_index++;
        }
    }

    for(i=0; i < count_name-1 ; i++){
        for(j=i+1; j< count_name; j++)
        {
            if(strcmp(name[i],name[j]) > 0)
            {
                strcpy(temp,name[i]);
                strcpy(name[i],name[j]);
                strcpy(name[j],temp);
            }
        }
    }

    for (i = 0; i < count_name; i++){
        printf("%s\n", name[i]);
    }
}

- Brad Capehart

---

我已经搜索了很多。-- 我很难相信这一点。网络上有大量关于高效排序技术的可访问文本。 - Jim Balter

@JimBalter，我真的搜索了很多。我不知道你有什么问题。这是我分配的一个任务，关于在C语言中以特定方式排序。我不能提供任何解决方案。请认为我很蠢并给我一个解决方案链接？ - Brad Capehart

“我不知道你有什么问题。” -- 噢，好的。 - Jim Balter

这里有很多回答，只有一个认识到问题的扭曲之处，即排序不是标准的。提问者希望小写字母排在大写字母之前。提问者的老师非常聪明，这是一个很好的作业。 - O. Jones

分配任务？我每天都遇到这个现实世界的问题。按照我想要的方式对我的杂货清单进行排序真是一件真正的麻烦事。 - David C. Rankin

Answer 1

将相似的单词放在一起...

对于单词列表，通常更有用的是将“相同”的单词（即使它们在大小写上不同）分组在一起。例如：

Keeping things together:          Simple "M after m":
------------------------          -------------------
mars                              mars
mars bar                          mars bar
Mars bar                          milk
milk                              milk-duds
Milk                              milky-way
milk-duds                         Mars bar
milky-way                         Milk
Milky-way                         Milky-way

如果您想要像第一列那样排列字词，我提供三种方法：

• 使用strcasecmp()和strcmp()组合。
• 使用isalpha()、tolower()和isupper()跟踪字符类型的单次传递实现。
• 利用整理表的单遍实现。

最后，我讨论了两个替代方案：

• 使用整理表建立任意排序。
• 将语言环境设置为使用基于语言环境的整理。

使用可用的库函数

如果可能的话，避免重复造轮子。在这种情况下，我们可以通过使用POSIX函数strcasecmp()进行不区分大小写的比较，如果它们相等，则回退到strcmp()。

int alphaBetize (const char *a, const char *b) {
    int r = strcasecmp(a, b);
    if (r) return r;
    /* if equal ignoring case, use opposite of strcmp() result to get
     * lower before upper */
    return -strcmp(a, b); /* aka: return strcmp(b, a); */
}

（在某些系统中，大小写不敏感的比较函数被称为stricmp()或_stricmp()。如果您无法使用其中之一，则下面提供了一个实现。）

#ifdef I_DONT_HAVE_STRCASECMP
int strcasecmp (const char *a, const char *b) {
    while (*a && *b) {
        if (tolower(*a) != tolower(*b)) {
            break;
        }
        ++a;
        ++b;
    }
    return tolower(*a) - tolower(*b);
}
#endif

避免两次字符串比较

有时候，现有的函数性能不够好，你需要采取其他方法来提高速度。以下函数以单次比较方式进行比较，并且不使用strcasecmp()或strcmp()。但是它将所有非字母字符视为比字母小。

int alphaBetize (const char *a, const char *b) {
    int weight = 0;
    do {
        if (*a != *b) {
            if (!(isalpha(*a) && isalpha(*b))) {
                if (isalpha(*a) || isalpha(*b)) {
                    return isalpha(*a) - isalpha(*b);
                }
                return *a - *b;
            }
            if (tolower(*a) != tolower(*b)) {
                return tolower(*a) - tolower(*b);
            }
            /* treat as equal, but mark the weight if not set */
            if (weight == 0) {
                weight = isupper(*a) - isupper(*b);
            }
        }
        ++a;
        ++b;
    } while (*a && *b);
    /* if the words compared equal, use the weight as tie breaker */
    if (*a == *b) {
        return weight;
    }
    return !*b - !*a;
}

使用此比较排序将保持milk和Milk彼此相邻，即使列表中包含milk-duds。

使用排序表

这里有一种从“配置”动态创建排序表的方法。它用于说明一种对比技术，以改变字符串比较的方式。

您可以使用一种简单的表来描述字母（或除NUL字节外的任何字符）希望具有的相对顺序，从而映射字母表如何进行比较：

const char * alphaBetical =
    "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";

通过这种排序方式，我们可以创建一个查找表来查看两个字母应该如何相互比较。以下函数将在第一次初始化表格时初始化表格，否则进行表格查找。

int alphaBeta_lookup (int c) {
    static int initialized;
    static char table[CHAR_MAX+1];
    if (!initialized) {
        /* leave all non-alphaBeticals in their relative order, but below
           alphaBeticals */
        int i, j;
        for (i = j = 1; i < CHAR_MAX+1; ++i) {
            if (strchr(alphaBetical, i)) continue;
            table[i] = j++;
        }
        /* now run through the alphaBeticals */
        for (i = 0; alphaBetical[i]; ++i) {
            table[(int)alphaBetical[i]] = j++;
        }
        initialized = 1;
    }
    /* return the computed ordinal of the provided character */
    if (c < 0 || c > CHAR_MAX) return c;
    return table[c];
}

有了这个查找表，我们现在可以简化alphaBetize()比较函数的循环体：

int alphaBetize (const char *a, const char *b) {
    int ax = alphaBeta_lookup(*a);
    int bx = alphaBeta_lookup(*b);
    int weight = 0;
    do {
        char al = tolower(*a);
        char bl = tolower(*b);
        if (ax != bx) {
            if (al != bl) {
                return alphaBeta_lookup(al) - alphaBeta_lookup(bl);
            }
            if (weight == 0) {
                weight = ax - bx;
            }
        }
        ax = alphaBeta_lookup(*++a);
        bx = alphaBeta_lookup(*++b);
    } while (ax && bx);
    /* if the words compared equal, use the weight as tie breaker */
    return (ax != bx) ? !bx - !ax : weight;
}

我们能让事情变得更简单吗？

使用排序表，您可以使用简化的比较函数创建许多不同的排序方式，例如：

int simple_collating (const char *a, const char *b) {
    while (alphaBeta_lookup(*a) == alphaBeta_lookup(*b)) {
        if (*a == '\0') break;
        ++a, ++b;
    }
    return alphaBeta_lookup(*a) - alphaBeta_lookup(*b);
}

使用相同的函数并通过修改alphaBetical字符串，您可以实现几乎任何想要的排序方式（字母顺序、反向字母顺序、元音字母在辅音字母之前等）。然而，保持相似单词在一起的排列需要将大写单词与小写单词交替出现，这只能通过忽略大小写进行比较来实现。

请注意，使用上面的simple_collating()函数和我提供的alphaBetical字符串，Bacon将出现在milk之前，但Mars将出现在milk之后且在Milk之前。

如果你想根据你的语言环境进行排序。

如果您想使用已经为您的语言环境定义的排序序列，您可以设置区域设置并调用排序比较函数：

/*
 * To change the collating locale, use (for example):
       setlocale(LC_COLLATE, "en.US");
 */
int iso_collating (const char *a, const char *b) {
    return strcoll(a, b);
}

现在，通过更改语言环境，排序顺序将基于标准化的排列顺序。

- jxh

---

不，我完全没有这样说。我只是在说它使用了一个名为strcasecmp的函数，而这个函数在C语言的任何标准库中都找不到。所谓标准库，是指任何C编译器都具备的标准库。然而，对于第二段代码块，我很抱歉，我想我有点草率了，没有意识到它根本没有被使用。 - Utkan Gezer

我并不是不能写一个类似的，但是无论如何也没有必要再进一步讨论了。我猜想（至少希望）重点已经传达出去了。 - Utkan Gezer

@ThoAppelsin：我已经为您提供了一个实现。祝好！ - jxh

偏爱使用现有库函数而不是自定义比较的解决方案不仅可以防止“重复造轮子”，而且可以轻松地与本地化例程交换，例如Windows的[CompareStringEx]（http://msdn.microsoft.com/en-us/library/windows/desktop/dd317761(v=vs.85).aspx）。 - Jongware

这个是正确的选择。但请注意，strcoll 在大多数情况下无法正常工作。尝试使用 setcoll 与列表 "bacon"、"Bacon"、"éclair"、"Éclair"、"spinach"。无论您如何设置 setlocale，它仍会在 spinach 之后对 éclair 进行整理（呕吐！）。 - dawg

Answer 2

你可以编写自定义比较函数来进行排序。

首先，看一下默认的strcmp排序顺序：

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

const char *tgt[]={
    "bacon", "Bacon", "mIlk", "Milk", "spinach", "MILK", "milk", "eggs"
};
int tgt_size=8;

static int cmp(const void *p1, const void *p2){
    return strcmp(* (char * const *) p1, * (char * const *) p2);
}

int main(int argc, char *argv[]) {
    printf("Before sort:\n\t");
    for(int n=0; n<tgt_size; n++)
        printf("%s ", tgt[n]);

    qsort(tgt, tgt_size, sizeof(char *), cmp);

    printf("\nAfter sort:\n\t");
    for(int n=0; n<tgt_size; n++)
        printf("%s ", tgt[n]);

    return 0;
}

strcmp 按照 ASCII 字符码排序；也就是说，它会先排序 A-Z，然后再排序 a-z，所以所有大写字母 A-Z 都排在任何带有小写字母的单词之前：

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    Bacon MILK Milk bacon eggs mIlk milk spinach 

我们可以编写自己的比较函数，用于在qsort中使用的cmp，它忽略大小写。代码如下：

int mycmp(const char *a, const char *b) {
    const char *cp1 = a, *cp2 = b;

    for (; toupper(*cp1) == toupper(*cp2); cp1++, cp2++)
        if (*cp1 == '\0')
            return 0;
    return ((toupper(*cp1) < toupper(*cp2)) ? -1 : +1);
} 

一定要将cmp也更改为：

static int cmp(const void *p1, const void *p2){
    return mycmp(* (char * const *) p1, * (char * const *) p2);
}

忽略大小写的版本现在打印出：

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    bacon Bacon eggs Milk MILK milk mIlk spinach 

这是使用POSIX函数strcasecmp获得的相同输出。

函数mycmp 首先按照正常顺序在字典中比较[a|A]-[z|Z]。这意味着您将得到类似字母的单词，但您可能会像Bacon, bacon一样得到bacon, Bacon。这是因为qsort不是stable sort，而“Bacon”与“bacon”相等。

现在我们想要的是，如果忽略大小写时比较为0（即，像'MILK'和'milk'一样的相同单词），现在包括大小写并反转顺序进行比较：

int mycmp(const char *a, const char *b) {
    const char *cp1 = a, *cp2 = b;
    int sccmp=1;

    for (; toupper(*cp1) == toupper(*cp2); cp1++, cp2++)
        if (*cp1 == '\0')
            sccmp = 0;
    if (sccmp) return ((toupper(*cp1) < toupper(*cp2)) ? -1 : +1);

    for (; *a == *b; a++, b++)
        if (*a == '\0')
            return 0;
    return ((*a < *b) ? +1 : -1);
}

最终版本打印：

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    bacon Bacon eggs milk mIlk Milk MILK spinach 

很遗憾，这种方法在UNICODE上变得难以操作。对于复杂的排序，请考虑使用映射或多步排序与稳定排序一起使用。

对于复杂和位置感知的字母排序，请考虑使用Unicode排序。例如，在不同的位置，字母的排序方式不同。

Swedish                      z < ö
                             y == w
German                       ö < z
Danish                       Z < Å
Lithuanian                   i < y < k
Tr German                    ä == æ
Tr Spanish                   c < ch < d   
German Dictionary Sort:      of < öf
German Phonebook Sort:       öf < of

这些区别的默认值被收录在默认的Unicode排序元素表(DUCET)中，该表为UNICODE排序和字符串比较提供了默认映射。您可以修改默认值以捕获字典排序和电话簿排序之间的差异、不同位置或大小写处理的不同处理方式。个别位置变化在Unicode通用语言环境数据存储库(CLDR)中得到积极跟踪。

多级排序的建议是分层的：

Level   Description           Examples
L1      Base characters       role < roles < rule
L2      Accents               role < rôle < roles
L3      Case/Variants         role < Role < rôle
L4      Punctuation           role < “role” < Role
Ln      Identical             role < ro□le < “role”

Unicode排序的广泛应用是在ICU库中实现的。几个示例的默认DUCET排序如下：

b < B < bad < Bad < bäd
c < C < cote < coté < côte < côté 

您可以使用ICU Explorer探索ICU库并更改位置和目标。

如果您想为了好玩而实现自己的DUCET版本，可以按照此Python脚本中使用的一般方法进行操作。它并不是无法理解，但也不是琐碎的。

- dawg

---

@Jongware：我修复了它。感谢你指出来。这实际上是一个非常有趣的问题... - dawg

没问题。这实际上导致了问题的“正确”答案：使用ICU库。 - dawg

L3的已记录示例本身就不直观。我理解它，但这不是我认为理想的顺序。 - jxh

@ThoAppelsin：你能想出一个这里使用的算法不起作用的情况吗？否则你只是在毫无根据地批评... - dawg

@dawg 我已经有了：Intel vs. intelligence。在大写和小写字母中，I 和 i 是同一个字母。根据问题，小写字母必须先出现，因此 intelligence 应该获胜并排在前面。然而，根据你的排序逻辑，Intel 排在第一位。你的排序逻辑可能是 Unicode 的，也可能是直观的，但不是问题描述中的那个。 - Utkan Gezer

Answer 3

我来晚了，不指望能一举拿下这个奖品，但看到没有使用我首选的习语解决方案，想参与一下讨论。

当我阅读问题规范时，我的第一个想法是某种自定义排序顺序，在 @jxh 的使用排序表概念中基本上找到了这种方式。我认为大小写不敏感并不是核心概念，只是一种奇怪的排序方法。

因此，我提供以下代码作为另一种实现方式。它只适用于 glibc - 使用 qsort_r(3) - 但感觉像是一种更轻量级的方法，并支持运行时的许多排序序列。但我进行了轻微的测试，很可能遗漏了各种弱点。其中之一：我没特别注意 Unicode 或一般的宽字符领域，避免负数数组下标的无符号字符强制转换看起来可疑。

#include <stdio.h>
#include <limits.h>

/*
 * Initialize an index array associated with the collating
 * sequence in co. The affected array can subsequently be
 * passed in as the final client data pointer into qsort_r
 * to be used by collating_compare below.
 */
int
collating_init(const char *co, int *cv, size_t n)
{
    const unsigned char *uco = (const unsigned char *) co;
    const unsigned char *s;
    size_t i;

    if (n <= UCHAR_MAX) {
        return -1;
    }
    for (i = 0; i < n; i++) {
        /* default for chars not named in the sequence */
        cv[i] = UCHAR_MAX;
    }
    for (s = uco; *s; s++) {
        /*
         * the "collating value" for a character's own
         * character code is its ordinal (starting from
         * zero) in the collating sequence. I.e., we
         * compare the values of cv['a'] and cv['A'] -
         * rather than 'a' and 'A' - to determine order.
         */
        cv[*s] = (s - uco);
    }

    return 0;
}

static int
_collating_compare(const char *str1, const char *str2, int *ip)
{
    const unsigned char *s1 = (const unsigned char *) str1;
    const unsigned char *s2 = (const unsigned char *) str2;

    while (*s1 != '\0' && *s2 != '\0') {
        int cv1 = ip[*s1++];
        int cv2 = ip[*s2++];

        if (cv1 < cv2) return -1;
        if (cv1 > cv2) return 1;
    }

    if (*s1 == '\0' && *s2 == '\0') {
        return 0;
    } else {
        return *s1 == '\0' ? -1 : 1;
    }
}

int
collating_compare(const void *v1, const void *v2, void *p)
{
    return _collating_compare(*(const char **) v1,
                              *(const char **) v2,
                              (int *) p);
}

前面的代码接近于可放在单独模块或库中的代码，但缺少自己的头文件（或在头文件中的入口）。我的测试仅将上下代码连接到一个名为custom_collate_sort.c的文件中，并使用。

gcc -DMAIN_TEST -Wall -o custom_collate_sort custom_collate_sort.c

...编译它。

#if defined(MAIN_TEST)

/* qsort_r is a GNU-ey thing... */

#define __USE_GNU
#include <stdlib.h>
#include <string.h>

#define NELEM(x) (sizeof x / sizeof 0[x])

static int
cmp(const void *v1, const void *v2)
{
    return strcmp(*(const char **) v1, *(const char **) v2);
}

static int
casecmp(const void *v1, const void *v2)
{
    return strcasecmp(*(const char **) v1, *(const char **) v2);
}

int
main(int ac, char *av[])
{
    size_t i;

    int cval[256], ret;
    int cval_rev[256], rret;

    char *tosort[] = {
        "cheeSE", "eggs", "Milk", "potatoes", "cheese", "spaghetti",
        "eggs", "milk", "spinach", "bacon", "egg", "apple", "PEAR",
        "pea", "berry"
    };

    ret = collating_init("aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVxXyYzZ",
                         cval, NELEM(cval));

    rret = collating_init("ZzYyXxVvUuTtSsRrQqPpOoNnMmLlKkJjIiHhGgFfEeDdCcBbAa",
                          cval_rev, NELEM(cval_rev));

    if (ret == -1 || rret == -1) {
        fputs("collating value array must accomodate an index of UCHAR_MAX\n", stderr);
        return 1;
    }

    puts("Unsorted:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort((void *) tosort, NELEM(tosort), sizeof tosort[0], cmp);

    puts("Sorted w/ strcmp:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort((void *) tosort, NELEM(tosort), sizeof tosort[0], casecmp);

    puts("Sorted w/ strcasecmp:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort_r((void *) tosort, NELEM(tosort), sizeof tosort[0],
            collating_compare, (void *) cval);

    puts("Sorted w/ collating sequence:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort_r((void *) tosort, NELEM(tosort), sizeof tosort[0],
            collating_compare, (void *) cval_rev);

    puts("Sorted w/ reversed collating sequence:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    return 0;
}

#endif /* MAIN_TEST */

- sjnarv

Answer 4

OP代码的关键在于使用函数strcmp()来比较两个字符串。
因此，我将从替换这个标准函数开始，使用另一个函数，如下所示：

  // We assume that the collating sequence satisfies the following rules:
  // 'A' < 'B' < 'C' < ...
  // 'a' < 'b' < 'c' < ...
  // We don't make any other assumptions.

  #include <ctype.h>      
  int my_strcmp(const char * s1, const char * s2)
  {
      const char *p1 = s1, *p2 = s2;
      while(*p1 == *p2 && *p1 != '\0' && *p2 != '\0')
          p1++, p2++;  /* keep searching... */

      if (*p1 == *p2)
         return 0;
      if (*p1 == '\0')
         return -1;
      if (*p2 == '\0')
         return +1;

      char c1 = tolower(*p1),      c2 = tolower(*p2);
      int  u1 = isupper(*p1) != 0, u2 = isupper(*p2) != 0;
      if (c1 != c2)
        return c1 - c2;  // <<--- Alphabetical order assumption is used here 
      if (c1 == c2)
        return u1 - u2;
  }

最后几行可以这样压缩：

     return (c1 != c2)? c1 - c2: u1 - u2;

现在，通过将strcmp()替换为my_strcmp()，您将得到所需的结果。

在排序算法中，将其主要方面分开考虑是一个好主意：

• 比较函数。
• 我们将使用的抽象排序算法。
• 当需要交换两个项目时，在数组中“移动”数据的方式。

这些方面可以独立优化。因此，例如，一旦你有了良好的比较函数，下一个优化步骤可能是用更有效率的算法（例如快速排序）来替换双重循环排序算法。标准库<stdlib.h>中的qsort()函数提供了这样的算法，因此您不需要担心编写它。最后，您用于存储数组信息的策略可能会影响性能。例如，将字符串存储为“指向char的指针数组”，而不是“char的数组数组”，因为交换指针比交换两个完整的字符数组更快。

指针数组

附加说明：前三个if()实际上是冗余的，因为以下语句的逻辑意味着在*p1或*p2为0的情况下会得到期望的结果。然而，保留这些if()可以使代码更易读。

- pablo1977

Answer 5

在这里，如果我理解正确的话，您想要一个不区分大小写的排序，在平局的情况下，使用“小写字母优先”的绑定条件。因此，它就像这样：

1. 忽略大小写，比较字母顺序：较早的字母在字母表中排在较后的字母之前。 2. 小写字母优先于大写字母。 3. 比较单词长度：短单词在长单词之前。

第二步仅在第一步没有区分任何内容时才执行。第三步将已经通过第一步检查。所有这些都要逐字逐句地完成，这意味着当对应字符之间出现平局时，您应该立即切换到第二步，而不仅仅是在整个字符串上平局时才切换到第二步。

假设我理解正确，我们现在需要编写一个函数，使其可以为任何给定的两个字符串进行比较。

#include <ctype.h>  // for tolower and islower

int my_character_compare(const char a, const char b)
{
    int my_result;

    my_result = tolower(a) - tolower(b);
    // unless it is zero, my_result is definitely the result here
    // Note: if any one of them was 0, result will also properly favour that one


    if (my_result == 0 && a != b)
    // if (could not be distinguished with #1, but are different)
    {
        // means that they are case-insensitively same
        // but different...
        // means that one of them are lowercase, the other one is upper
        if (islower(a))
            return -1;  // favour a
        else
            return 1;   // favour b
    }


    // regardless if zero or not, my_result is definitely just the result
    return my_result;
}

int my_string_compare(const char * a, const char * b)
{
    int my_result;

    my_result = my_character_compare(*a, *b);
    // unless it is zero, my_result is definitely the result here

    while (my_result == 0 && *a != 0)
    // current characters deemed to be same
    // if they are not both just 0 we will have to check the next ones
    {
        my_result = my_character_compare(*++a, *++b);
    }

    // whatever the my_result has been:
    //   whether it became != zero on the way and broke out of the loop
    //   or it is still zero, but we have also reached the end of the road/strings
    return my_result;
}

按照惯例，比较函数应该返回负值以支持第一个参数在前面，返回正值以支持第二个参数在前面，如果无法区分它们则返回零。这是额外的信息，你可能已经知道了如何使用strcmp。

就是这样！用my_string_compare替换代码中的strcmp，并将我们制作的这些定义放在顶部，即可得到正确的结果。确实，它为所讨论的示例输入提供了预期的结果。

当然，人们可以缩短这些定义，但我将它们制作得很长，以便更容易理解正在发生的事情。例如，我可以将它们全部简化为以下内容：

#include <ctype.h>

int my_string_compare(const char * a, const char * b)
{
    int my_result;

    while (*a || *b)
    {
        if ((my_result = tolower(*a) - tolower(*b)))
            return my_result;
        if (*a != *b)
            return (islower(*a)) ? -1 : 1;
        a++;
        b++;
    }

    return 0;
}

基本上与其他方法做的事情一样，你可以使用任何一种方法；或者更好地，自己编写一个。

- Utkan Gezer

---

@dawg 按照问题中描述的排序规则，将它们按顺序排列为 milk / mIlk / Milk。 - Utkan Gezer

@dawg 你可以在这里检查它的工作情况：http://ideone.com/ZtpC2H 我很想听一下它实际上不起作用的例子。而“不起作用”的意思是，执行的操作与问题描述相矛盾；不是按Unicode或任何其他人的意思来解释。 - Utkan Gezer

Answer 6

程序所需的标准头文件:

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

主程序从这里开始：

//Global Variables Required
//=========
const char *tgt[]={"bacon", "Bacon", "mIlk", 
        "Milk", "spinach", "MILK", "milk", "eggs"};    //Array for sorting
int tgt_size=8;                                        //Total Number of Records
int     SortLookupTable[128];                          //Custom sorting table
typedef int      cmp_t (const void *, const void *);




int main(int argc, char *argv[]) {
    printf("Before sort:\n\n");
    int n=0;
    for(n=0; n<tgt_size; n++)
        printf("%s\n", tgt[n]);

    CreateSortTable();

    myQsort(tgt, tgt_size, sizeof(char *), &compare);
    printf("\n\n====\n\n");
    for(n=0; n<tgt_size; n++)
        printf("%s\n", tgt[n]);

    return 0;
}

根据需求定制排序表格：

void CreateSortTable(void){
    int     i;
    for (i = 0; i < 128; i++){
        SortLookupTable[i] = 0;
    }
    char *s;
    s=(char *)malloc(64);
    memset(s, 0, 64);
    strcpy(s, "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ");

    i=1;
    for (; *s; s++){
        SortLookupTable[(int) ((unsigned char) *s)]=i;
        i++;
    }
}

快速排序算法，您也可以使用标准库提供的方法：

//Some important Definations required by Quick Sort
=======
#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
    es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;

#define swap(a, b)                          \
    if (swaptype == 0) {                    \
        long t = *(long *)(a);              \
        *(long *)(a) = *(long *)(b);        \
        *(long *)(b) = t;                   \
    } else                                  \
        swapfunc(a, b, es, swaptype)

#define vecswap(a, b, n)    if ((n) > 0) swapfunc(a, b, n, swaptype)


#define swapcode(TYPE, parmi, parmj, n) {       \
    long i = (n) / sizeof (TYPE);               \
    register TYPE *pi = (TYPE *) (parmi);       \
    register TYPE *pj = (TYPE *) (parmj);       \
    do {                                        \
        register TYPE   t = *pi;                \
        *pi++ = *pj;                            \
        *pj++ = t;                              \
        } while (--i > 0);                      \
}

#define min(a, b)   (a) < (b) ? a : b


//Other important function
void swapfunc(char *a, char *b, int n, int swaptype){
    if(swaptype <= 1)
        swapcode(long, a, b, n)
    else
        swapcode(char, a, b, n)
}

char * med3(char *a, char *b, char *c, cmp_t *cmp){
    if ( cmp(a, b) < 0){
        if (cmp(b, c) < 0){
            return b;
        }else{
            if ( cmp(a, c) < 0){

                return c;
            }else{
                return a;
            }
        }
    }else{
        if (cmp(b, c) < 0){
            return b;
        }else{
            if ( cmp(a, c) < 0){
                return a;
            }else{
                return c;
            }
        }
    }
}

//Custom Quick Sort

void myQsort(void *a, unsigned int n, unsigned int es, cmp_t *cmp){
    char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
    int d, r, swaptype, swap_cnt;

loop:   SWAPINIT(a, es);
    swap_cnt = 0;
    if (n < 7) {
        for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
            for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; pl -= es){
                swap(pl, pl - es);
            }
        return;
    }
    pm = (char *)a + (n / 2) * es;
    if (n > 7) {
        pl = a;
        pn = (char *)a + (n - 1) * es;
        if (n > 40) {
            d = (n / 8) * es;
            pl = med3(pl, pl + d, pl + 2 * d, cmp);
            pm = med3(pm - d, pm, pm + d, cmp);
            pn = med3(pn - 2 * d, pn - d, pn, cmp);
        }
        pm = med3(pl, pm, pn, cmp);
    }
    swap(a, pm);
    pa = pb = (char *)a + es;

    pc = pd = (char *)a + (n - 1) * es;
    for (;;) {
        while (pb <= pc && (r = cmp(pb, a)) <= 0) {
            if (r == 0) {
                swap_cnt = 1;
                swap(pa, pb);
                pa += es;
            }
            pb += es;
        }
        while (pb <= pc && (r = cmp(pc, a)) >= 0) {
            if (r == 0) {
                swap_cnt = 1;
                swap(pc, pd);
                pd -= es;
            }
            pc -= es;
        }
        if (pb > pc)
            break;
        swap(pb, pc);
        swap_cnt = 1;
        pb += es;
        pc -= es;
    }
    if (swap_cnt == 0) {  /* Switch to insertion sort */
        for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
            for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
                 pl -= es)
                swap(pl, pl - es);
        return;
    }

    pn = (char *)a + n * es;
    r = min(pa - (char *)a, pb - pa);
    vecswap(a, pb - r, r);
    r = min(pd - pc, pn - pd - es);
    vecswap(pb, pn - r, r);
    if ((r = pb - pa) > es)
        myQsort(a, r / es, es, cmp);
    if ((r = pd - pc) > es) {
        /* Iterate rather than recurse to save stack space */
        a = pn - r;
        n = r / es;
        goto loop;
    }
}

两个最重要的功能是：

unsigned char Change(char a){
    return (unsigned char ) SortLookupTable[(int)a];
}


int compare (const void *a, const void *b){
    char *s1= *(char **)a;
    char *s2= *(char **)b;
    int ret, len, i;
    ret=0;

    if (strlen((void*)s1) > strlen((void*)s2)){
        len=strlen((void*)s1);
    }else{
        len=strlen((void*)s2) ;
    }

    for(i=0; i<len; i++){
        if ( s1[i] != s2[i]){
            if ( Change(s1[i]) < Change(s2[i]) ){
                ret=0;
                break;
            }else{
                ret=1;
                break;
            }
        }
    }

    return ret;
}

- Vineet1982