Как реализовать алгоритм естественной сортировки в С++?
-
22-07-2019 - |
Вопрос
Я сортирую строки, состоящие из текста и чисел.Я хочу, чтобы сортировка сортировала части числа как числа, а не буквенно-цифровые.
Например, я хочу:abc1def, ..., abc9def, abc10def
вместо:abc10def, abc1def, ..., abc9def
Кто-нибудь знает алгоритм для этого (в частности, на С++)
Спасибо
Решение
Я спросил именно этот вопрос (хотя и на Java) и мне указали на http://www.davekoelle.com/alphanum.html у которого есть алгоритм и его реализации на многих языках.
Другие советы
Это известно как естественная сортировка.Есть алгоритм здесь это выглядит многообещающе.
Будьте осторожны с проблемами, связанными с символами, отличными от ASCII (см. запись в блоге Джеффа на предмет).
Доступно несколько реализаций естественной сортировки для C++.Краткий обзор:
natural_sort<>
- на основе Boost.Regex.- По моим тестам, он примерно в 20 раз медленнее, чем другие варианты.
- Дирк Ягдманн
alnum.hpp
, на основе книги Дэйва Кёлля буквенно-цифровой алгоритм- Потенциальные проблемы переполнения целых чисел для значений выше MAXINT.
- Мартин Пул
natsort
- написан на C, но легко может быть использован на C++.- Единственная реализация C/C++, которую я видел, предлагает версию без учета регистра, которая, казалось бы, имеет высокий приоритет для «естественной» сортировки.
- Как и другие реализации, он на самом деле не анализирует десятичные точки, а обрабатывает ведущие нули в особом случае (все, что начинается с 0, считается дробью), что немного странно, но потенциально полезно.
- PHP использует этот алгоритм.
Частичный репост мой еще один ответ:
bool compareNat(const std::string& a, const std::string& b){
if (a.empty())
return true;
if (b.empty())
return false;
if (std::isdigit(a[0]) && !std::isdigit(b[0]))
return true;
if (!std::isdigit(a[0]) && std::isdigit(b[0]))
return false;
if (!std::isdigit(a[0]) && !std::isdigit(b[0]))
{
if (a[0] == b[0])
return compareNat(a.substr(1), b.substr(1));
return (toUpper(a) < toUpper(b));
//toUpper() is a function to convert a std::string to uppercase.
}
// Both strings begin with digit --> parse both numbers
std::istringstream issa(a);
std::istringstream issb(b);
int ia, ib;
issa >> ia;
issb >> ib;
if (ia != ib)
return ia < ib;
// Numbers are the same --> remove numbers and recurse
std::string anew, bnew;
std::getline(issa, anew);
std::getline(issb, bnew);
return (compareNat(anew, bnew));
}
toUpper()
функция:
std::string toUpper(std::string s){
for(int i=0;i<(int)s.length();i++){s[i]=toupper(s[i]);}
return s;
}
Использование:
std::vector<std::string> str;
str.push_back("abc1def");
str.push_back("abc10def");
...
std::sort(str.begin(), str.end(), compareNat);
Чтобы решить то, что по сути является проблемой синтаксического анализа, конечный автомат (он же конечный автомат) это путь.Неудовлетворенный вышеупомянутыми решениями, я написал простой однопроходный алгоритм раннего спасения, который превосходит предложенные выше варианты C/C++ с точки зрения производительности, не страдает от ошибок переполнения числовых типов данных и легко модифицируется, чтобы добавить нечувствительность к регистру, если это необходимо. .
источники можно найти здесь
// -1: s0 < s1; 0: s0 == s1; 1: s0 > s1
static int numericCompare(const string &s0, const string &s1) {
size_t i = 0, j = 0;
for (; i < s0.size() && j < s1.size();) {
string t0(1, s0[i++]);
while (i < s0.size() && !(isdigit(t0[0]) ^ isdigit(s0[i]))) {
t0.push_back(s0[i++]);
}
string t1(1, s1[j++]);
while (j < s1.size() && !(isdigit(t1[0]) ^ isdigit(s1[j]))) {
t1.push_back(s1[j++]);
}
if (isdigit(t0[0]) && isdigit(t1[0])) {
size_t p0 = t0.find_first_not_of('0');
size_t p1 = t1.find_first_not_of('0');
t0 = p0 == string::npos ? "" : t0.substr(p0);
t1 = p1 == string::npos ? "" : t1.substr(p1);
if (t0.size() != t1.size()) {
return t0.size() < t1.size() ? -1 : 1;
}
}
if (t0 != t1) {
return t0 < t1 ? -1 : 1;
}
}
return i == s0.size() && j == s1.size() ? 0 : i != s0.size() ? 1 : -1;
}
Я не совсем уверен, что вам это нужно, в любом случае вы можете попробовать :-)