对字符串数组进行不区分大小写的排序

Question

基本上，我必须使用选择排序来排序string[]。我已经完成了这部分，但这是我遇到的困难。

但是，排序应该不区分大小写，这样 "antenna" 就会排在 "Jupiter" 之前。 ASCII 从大写到小写排序，那么就没有办法只交换排序后的字符串的顺序吗？或者有更简单的解决方案吗？

void stringSort(string array[], int size) {
    int startScan, minIndex;
    string minValue;

    for(startScan = 0 ; startScan < (size - 1); startScan++) {
        minIndex = startScan;
        minValue = array[startScan];

        for (int index = startScan + 1; index < size; index++) {
            if (array[index] < minValue) {
                minValue = array[index];
                minIndex = index;
            }
        }
        array[minIndex] = array[startScan];
        array[startScan] = minValue;
    }
}

Answer 1

您可以对您比较的每个字符调用 tolower。这可能是最简单但不是很好的解决方案，因为：

您多次查看每个字符，因此您会比必要更频繁地调用该方法
您需要格外小心地处理宽字符 w.r.t 及其编码（UTF8 等）

您也可以将比较器替换为您自己的函数。 IE。在某些地方，您可以比较 stringone[i] < stringtwo[j] 或 charA < charB 之类的内容。将其更改为 my_less_than(stringone[i], stringtwo[j]) 并实施您想要的确切顺序。

另一种方法是将每个字符串转换为小写一次并创建一个对数组。然后你只根据小写值进行比较，但你交换整对，这样你的最终字符串也会以正确的顺序排列。

最后，您可以创建一个小写版本的数组并对这个数组进行排序。每当你交换这个中的两个元素时，你也会交换原始数组。

请注意，所有这些提案仍然需要正确处理宽字符（如果您需要的话）

Answer 2

C++ 为您提供了 sort，它采用比较函数。在您使用 vector<string> 的情况下，您将比较两个字符串。如果第一个参数较小，比较函数应该 return true。

对于我们的比较函数，我们希望在 tolower has been applied. To do this we can use mismatch 之后的 string 之间找到第一个不匹配的字符，它在两个字符 returning [=15= 之间进行比较] 只要相等即可：

const auto result = mismatch(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), [](const unsigned char lhs, const unsigned char rhs){return tolower(lhs) == tolower(rhs);});

要确定 lhs 是否小于送入 mismatch 的 rhs，我们需要测试 3 件事：

string 是否长度不等
string lhs 变短了
或者 lhs 中第一个不匹配的 char 是否小于 rhs

char

此评估可以由以下人员执行：

result.second != rhs.cend() && (result.first == lhs.cend() || tolower(*result.first) < tolower(*result.second));

最终，我们希望将其包装在一个 lambda 中，并将其作为我们的比较器插回 sort：

sort(foo.begin(), foo.end(), [](const unsigned char lhs, const unsigned char rhs){
    const auto result = mismatch(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), [](const unsigned char lhs, const unsigned char rhs){return tolower(lhs) == tolower(rhs);});

    return result.second != rhs.cend() && (result.first == lhs.cend() || tolower(*result.first) < tolower(*result.second));
});

这将正确排序 vector<string> foo。你可以在这里看到一个活生生的例子：http://ideone.com/BVgyD2

编辑：

刚刚看到您的问题更新。您也可以将 sort 与 string array[] 一起使用。你只需要这样称呼它：sort(array, std::next(array, size), ...

Answer 3

使用不区分大小写的字符串比较函数代替 < 运算符。

C89/C99 提供 strcoll（字符串整理），它进行区域设置感知字符串比较。它在 C++ 中可用 std::strcoll。在某些（大多数？）语言环境中，例如 en_CA.UTF-8、A 和 a（以及其中任何一个的所有重音形式）处于相同的等价状态 class。我认为 strcoll 仅在等价 class 内进行比较，如果整个字符串在其他方面相等，则作为平局，这与不区分大小写的比较给出了非常相似的排序顺序。排序规则（至少在 GNU/Linux 的英语语言环境中）会忽略一些字符（如 [）。所以 ls /usr/share | sort 给出类似

的输出

acpi-support
adduser
ADM_scripts
aglfn
aisleriot

我通过 sort 进行管道处理，因为 ls 进行了自己的排序，这与 sort 基于区域设置的排序不太一样。

如果您想将一些用户输入的任意字符串排序为用户将直接看到的顺序，区域设置感知字符串比较通常就是您想要的。仅在大小写或重音上不同的字符串不会比较相等，因此如果您使用稳定排序并根据区分大小写的字符串比较相等，这将不起作用，否则您会得到不错的结果。根据用例，比普通的不区分大小写的比较更好。

FreeBSD's strcoll 对于 POSIX (ASCII) 以外的语言环境过去是并且可能仍然是区分大小写的。该论坛 post 建议在大多数其他系统上不区分大小写。

MSVC 为不区分大小写的排序规则提供了 _stricoll，这意味着其正常的 strcoll 区分大小写。然而，这可能只是意味着在等价 class 内进行比较的回退不会发生。也许有人可以用 MSVC 测试下面的例子。

// strcoll.c: show that these strings sort in a different order, depending on locale
#include <stdio.h>
#include <locale.h>

int main()
{
    // TODO: try some strings containing characters like '[' that strcoll ignores completely.
    const char * s[] = { "FooBar - abc", "Foobar - bcd", "FooBar - cde" };
#ifdef USE_LOCALE
    setlocale(LC_ALL, ""); // empty string means look at env vars
#endif
    strcoll(s[0], s[1]);
    strcoll(s[0], s[2]);
    strcoll(s[1], s[2]);
    return 0;
}

gcc -DUSE_LOCALE -Og strcoll.c && ltrace ./a.out（或运行 LANG=C ltrace a.out）的输出：

__libc_start_main(0x400586, 1, ...
setlocale(LC_ALL, "")                        = "en_CA.UTF-8"   # my env contains LANG=en_CA.UTF-8
strcoll("FooBar - abc", "Foobar - bcd")      = -1
strcoll("FooBar - abc", "FooBar - cde")      = -2
strcoll("Foobar - bcd", "FooBar - cde")      = -1
  # the three strings are in order
+++ exited (status 0) +++

与 gcc -Og -UUSE_LOCALE strcoll.c && ltrace ./a.out:

__libc_start_main(0x400536, ...
# no setlocale, so current locale is C
strcoll("FooBar - abc", "Foobar - bcd")      = -32
strcoll("FooBar - abc", "FooBar - cde")      = -2
strcoll("Foobar - bcd", "FooBar - cde")      = 32   # s[1] should sort after s[2], so it's out of order
+++ exited (status 0) +++

POSIX.1-2001 提供 strcasecmp。 POSIX 规范说结果是 "unspecified" 除了纯 ASCII 以外的语言环境，所以我不确定常见的实现是否正确处理 utf-8。

参见 this post for portability issues with strcasecmp, e.g. to Windows。有关执行不区分大小写的字符串比较的其他 C++ 方法，请参阅该问题的其他答案。

一旦你有了不区分大小写的比较函数，你就可以将它与其他排序算法一起使用，比如 C 标准库 qsort，或 c++ std::sort，而不是编写自己的 O(n^2) 选择排序。

正如 b.buchhold 的回答所指出的那样，即时进行不区分大小写的比较可能比将所有内容都转换为小写一次并对索引数组进行排序要慢。多次需要每个字符串的小写版本。 std::strxfrm 将转换一个字符串，以便结果的 strcmp 将给出与原始字符串的 strcoll 相同的结果。

Answer 4

这个解决方案比 Jonathan Mee 的解决方案更容易理解，而且效率很低，但出于教育目的可能没问题：

std::string lowercase( std::string s )
{
   std::transform( s.begin(), s.end(), s.begin(), ::tolower );
   return s;
}

std::sort( array, array + length, 
           []( const std::string &s1, const std::string &s2 ) { 
               return lowercase( s1 ) < lowercase( s2 ); 
           } );

如果你必须使用你的排序功能，你可以使用相同的方法：

    ....
    minValue = lowercase( array[startScan] );

    for (int index = startScan + 1; index < size; index++) {
        const std::string &tstr = lowercase( array[index] );
        if (tstr < minValue) {
            minValue = tstr;
            minIndex = index;
        }
    }
    ...

Answer 5

我使用这个 lambda 函数对字符串向量进行排序：

std::sort(entries.begin(), entries.end(), [](const std::string& a, const std::string& b) -> bool {
        for (size_t c = 0; c < a.size() and c < b.size(); c++) {
            if (std::tolower(a[c]) != std::tolower(b[c]))
                return (std::tolower(a[c]) < std::tolower(b[c]));
        }
        return a.size() < b.size();
    });

Answer 6

#include <algorithm>
#include <vector>
#include <string>

using namespace std;    

void CaseInsensitiveSort(vector<string>& strs)
{
    sort(
        begin(strs),
        end(strs),
        [](const string& str1, const string& str2){
            return lexicographical_compare(
                begin(str1), end(str1),
                begin(str2), end(str2),
                [](const char& char1, const char& char2) {
                    return tolower(char1) < tolower(char2);
                }
            );
        }
    );
}

对字符串数组进行不区分大小写的排序

Case insensitive sorting of an array of strings

c++

sorting

string

case-insensitive