對字符串數組進行不區分大小寫排序

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