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

Question

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

然而，排序应该不区分大小写，以便“天线”会在“木星”之前出现。 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

C++提供了sort这需要一个比较函数。在你的情况下，你会比较两个字符串。如果第一个参数较小，比较函数应返回true。

对于我们的比较功能，我们希望在tolower已应用后找到string之间的第一个不匹配字符。要做到这一点，我们可以使用mismatch这需要两个字符返回true之间的比较，只要他们是平等的：

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

，以决定是否lhs比送入mismatch我们需要测试3件事情rhs小：

1. 进行了string小号不等长
2. 当时string lhs短
3. 或者是第一英里从比第一不匹配charlhs小从rhs

这种评价smatched char可以通过执行：

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

最终，我们将要在一个lambda来包装这件事，然后重新插入到sort作为我们的比较：

sort(foo.begin(), foo.end(), [](const auto& lhs, const auto& rhs){ 
    const auto result = mismatch(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), [](const auto& lhs, const auto& 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, array + length, ...

Answer 2

您可以在每个你比较的字符上拨打tolower。这可能是最简单的，尚不能很好的解决方案，becasue：

• 你看每一个字符多次，所以你会更经常调用的方法不是必要
• 你需要格外小心处理宽字符与他们的编码（UTF8等）

你也可以用你自己的函数替换比较器。即会出现一些地方，比如stringone[i] < stringtwo[j]或charA < charB。将其更改为my_less_than(stringone[i], stringtwo[j])并实施您想要的确切排序。

另一种方法是将每个字符串转换为小写一次并创建一个数组对。那么你只将你的比较基于小写值，但是你交换整个对，这样你的最终字符串也会按照正确的顺序排列。

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

注意，所有这些建议仍然需要的宽字符妥善处理（如果需要，在所有）

Answer 3

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

C89/C99提供strcoll（字符串整理），它进行了区域设置意识的字符串比较。它可以在C++中作为std::strcoll提供。在一些（大多数？）语言环境中，如en_CA.UTF-8,A和a（以及任一个的所有重音形式）都处于相同的等价类中。我认为如果整个字符串在其他方面是相等的，那么strcoll只会在等价类中进行比较，这会给与大小写不敏感的比较类似的排序顺序。排序规则（至少在GNU/Linux的英文语言环境中）会忽略某些字符（如[）。所以ls /usr/share | sort通过sort给像

acpi-support 
adduser 
ADM_scripts 
aglfn 
aisleriot 

我管输出，因为ls做它自己的排序，这是不完全一样sort的基于地区的排序。

如果您想将某些用户输入的任意字符串排序为用户直接看到的顺序，则区域设置感知的字符串比较通常是您想要的。只有大小写或重音不同的字符串不会比较相等，因此如果您使用稳定的排序并根据不同字符串比较相等的字符串，则不起作用，但否则您会得到不错的结果。根据使用情况，比简单的大小写不敏感的比较更好。

FreeBSD's strcoll过去了，可能对POSIX（ASCII）以外的区域还是区分大小写。该论坛帖子表明，在大多数其他系统上，它是而不是案例敏感。

MSVC为不区分大小写的校对提供了一个_stricoll，意味着它的正常strcoll区分大小写。然而，这可能意味着等值类内的比较不会发生。也许有人可以用MSVC测试下面的例子。

__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：gcc -DUSE_LOCALE -Og strcoll.c && ltrace ./a.out（或运行LANG = C ltrace a.out的）输出的

---

// 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; 
} 

__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规范说结果对于除纯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

这个解决方案要简单得多比乔纳森眉的和非常低效理解，但对于教育的目的可能是罚款：

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])) 
      continue; 
     if (std::tolower(a[c]) < std::tolower(b[c])) 
      return true; 
     else 
      return false; 
    } 
    return a.size() < b.size(); 
}); 

PS：我现在没有在我面前的代码，所以没有测试，但我会检查它，当我可以。

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); 
       } 
      ); 
     } 
    ); 
}