我正在对由文本和数字组成的字符串进行排序。我希望排序将数字部分排序为数字，而不是字母数字。
例如我想要：abc1def, ..., abc9def, abc10def
而不是：abc10def，abc1def，...，abc9def
有谁知道这方面的算法（特别是在 C++ 中）
谢谢
Will
问问题
13700 次
9 回答
17
我问了这个确切的问题（尽管是在 Java 中）并被指向http://www.davekoelle.com/alphanum.html，它有一个算法和多种语言的实现。
于 2009-03-13T11:31:41.907 回答
8
有几种 C++ 的自然排序实现可用。简要回顾：
natural_sort<>- 基于 Boost.Regex。- 在我的测试中，它比其他选项慢大约 20 倍。
- Dirk Jagdmann 的
alnum.hpp，基于 Dave Koelle 的alphanum 算法- 超过 MAXINT 的值的潜在整数过低问题
- Martin Pool's
natsort- 用 C 编写，但在 C++ 中可以轻松使用。- 我见过的唯一 C/C++ 实现提供不区分大小写的版本，这似乎是“自然”排序的高优先级。
- 与其他实现一样，它实际上并不解析小数点，但它会处理特殊情况下的前导零（任何带有前导 0 的东西都被假定为分数），这有点奇怪但可能很有用。
- PHP 使用这种算法。
于 2014-11-05T19:43:49.840 回答
6
这称为自然排序。这里有一个看起来很有希望的算法。
小心非 ASCII 字符的问题（请参阅Jeff 的博客条目）。
于 2009-03-13T11:18:54.853 回答
2
部分转贴我的另一个答案：
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);
于 2015-11-15T20:36:53.183 回答
0
对于那些到达这里并且已经在他们的项目中使用 Qt 的人，您可以使用该QCollator课程。有关详细信息，请参阅此问题。
于 2020-08-05T15:48:10.713 回答
0
Avalanchesort 是自然排序的递归变体，它运行合并，同时探索排序数据的堆栈。即使您在算法运行/排序时将数据添加到排序堆，算法也会稳定排序。
搜索原理很简单。仅合并具有相同排名的运行。
在找到前两个自然运行（秩为 0）后，雪崩排序将它们合并为秩为 1 的运行。然后它调用雪崩排序，以生成第二次运行的秩为 1 并将两次运行合并为秩为 2 的运行。然后它调用avalancheSort 在未排序的数据上生成排名为 2 的运行....
我的实现porthd/avalanchesort将排序与使用接口注入的数据处理分开。您可以将算法用于数组、关联数组或列表等数据结构。
/**
* @param DataListAvalancheSortInterface $dataList
* @param DataRangeInterface $beginRange
* @param int $avalancheIndex
* @return bool
*/
public function startAvalancheSort(DataListAvalancheSortInterface $dataList)
{
$avalancheIndex = 0;
$rangeResult = $this->avalancheSort($dataList, $dataList->getFirstIdent(), $avalancheIndex);
if (!$dataList->isLastIdent($rangeResult->getStop())) {
do {
$avalancheIndex++;
$lastIdent = $rangeResult->getStop();
if ($dataList->isLastIdent($lastIdent)) {
$rangeResult = new $this->rangeClass();
$rangeResult->setStart($dataList->getFirstIdent());
$rangeResult->setStop($dataList->getLastIdent());
break;
}
$nextIdent = $dataList->getNextIdent($lastIdent);
$rangeFollow = $this->avalancheSort($dataList, $nextIdent, $avalancheIndex);
$rangeResult = $this->mergeAvalanche($dataList, $rangeResult, $rangeFollow);
} while (true);
}
return $rangeResult;
}
/**
* @param DataListAvalancheSortInterface $dataList
* @param DataRangeInterface $range
* @return DataRangeInterface
*/
protected function findRun(DataListAvalancheSortInterface $dataList,
$startIdent)
{
$result = new $this->rangeClass();
$result->setStart($startIdent);
$result->setStop($startIdent);
do {
if ($dataList->isLastIdent($result->getStop())) {
break;
}
$nextIdent = $dataList->getNextIdent($result->getStop());
if ($dataList->oddLowerEqualThanEven(
$dataList->getDataItem($result->getStop()),
$dataList->getDataItem($nextIdent)
)) {
$result->setStop($nextIdent);
} else {
break;
}
} while (true);
return $result;
}
/**
* @param DataListAvalancheSortInterface $dataList
* @param $beginIdent
* @param int $avalancheIndex
* @return DataRangeInterface|mixed
*/
protected function avalancheSort(DataListAvalancheSortInterface $dataList,
$beginIdent,
int $avalancheIndex = 0)
{
if ($avalancheIndex === 0) {
$rangeFirst = $this->findRun($dataList, $beginIdent);
if ($dataList->isLastIdent($rangeFirst->getStop())) {
// it is the last run
$rangeResult = $rangeFirst;
} else {
$nextIdent = $dataList->getNextIdent($rangeFirst->getStop());
$rangeSecond = $this->findRun($dataList, $nextIdent);
$rangeResult = $this->mergeAvalanche($dataList, $rangeFirst, $rangeSecond);
}
} else {
$rangeFirst = $this->avalancheSort($dataList,
$beginIdent,
($avalancheIndex - 1)
);
if ($dataList->isLastIdent($rangeFirst->getStop())) {
$rangeResult = $rangeFirst;
} else {
$nextIdent = $dataList->getNextIdent($rangeFirst->getStop());
$rangeSecond = $this->avalancheSort($dataList,
$nextIdent,
($avalancheIndex - 1)
);
$rangeResult = $this->mergeAvalanche($dataList, $rangeFirst, $rangeSecond);
}
}
return $rangeResult;
}
protected function mergeAvalanche(DataListAvalancheSortInterface $dataList, $oddListRange, $evenListRange)
{
$resultRange = new $this->rangeClass();
$oddNextIdent = $oddListRange->getStart();
$oddStopIdent = $oddListRange->getStop();
$evenNextIdent = $evenListRange->getStart();
$evenStopIdent = $evenListRange->getStop();
$dataList->initNewListPart($oddListRange, $evenListRange);
do {
if ($dataList->oddLowerEqualThanEven(
$dataList->getDataItem($oddNextIdent),
$dataList->getDataItem($evenNextIdent)
)) {
$dataList->addListPart($oddNextIdent);
if ($oddNextIdent === $oddStopIdent) {
$restTail = $evenNextIdent;
$stopTail = $evenStopIdent;
break;
}
$oddNextIdent = $dataList->getNextIdent($oddNextIdent);
} else {
$dataList->addListPart($evenNextIdent);
if ($evenNextIdent === $evenStopIdent) {
$restTail = $oddNextIdent;
$stopTail = $oddStopIdent;
break;
}
$evenNextIdent = $dataList->getNextIdent($evenNextIdent);
}
} while (true);
while ($stopTail !== $restTail) {
$dataList->addListPart($restTail);
$restTail = $dataList->getNextIdent($restTail);
}
$dataList->addListPart($restTail);
$dataList->cascadeDataListChange($resultRange);
return $resultRange;
}
}
于 2020-08-08T06:43:33.510 回答
0
我的算法带有java版本的测试代码。如果你想在你的项目中使用它，你可以自己定义一个比较器。
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.function.Consumer;
public class FileNameSortTest {
private static List<String> names = Arrays.asList(
"A__01__02",
"A__2__02",
"A__1__23",
"A__11__23",
"A__3++++",
"B__1__02",
"B__22_13",
"1_22_2222",
"12_222_222",
"2222222222",
"1.sadasdsadsa",
"11.asdasdasdasdasd",
"2.sadsadasdsad",
"22.sadasdasdsadsa",
"3.asdasdsadsadsa",
"adsadsadsasd1",
"adsadsadsasd10",
"adsadsadsasd3",
"adsadsadsasd02"
);
public static void main(String...args) {
List<File> files = new ArrayList<>();
names.forEach(s -> {
File f = new File(s);
try {
if (!f.exists()) {
f.createNewFile();
}
files.add(f);
} catch (IOException e) {
e.printStackTrace();
}
});
files.sort(Comparator.comparing(File::getName));
files.forEach(f -> System.out.print(f.getName() + " "));
System.out.println();
files.sort(new Comparator<File>() {
boolean caseSensitive = false;
int SPAN_OF_CASES = 'a' - 'A';
@Override
public int compare(File left, File right) {
char[] csLeft = left.getName().toCharArray(), csRight = right.getName().toCharArray();
boolean isNumberRegion = false;
int diff=0, i=0, j=0, lenLeft=csLeft.length, lenRight=csRight.length;
char cLeft = 0, cRight = 0;
for (; i<lenLeft && j<lenRight; i++, j++) {
cLeft = getCharByCaseSensitive(csLeft[i]);
cRight = getCharByCaseSensitive(csRight[j]);
boolean isNumericLeft = isNumeric(cLeft), isNumericRight = isNumeric(cRight);
if (isNumericLeft && isNumericRight) {
// Number start!
if (!isNumberRegion) {
isNumberRegion = true;
// Remove prefix '0'
while (i < lenLeft && cLeft == '0') i++;
while (j < lenRight && cRight == '0') j++;
if (i == lenLeft || j == lenRight) break;
}
// Diff start: calculate the diff value.
if (cLeft != cRight && diff == 0)
diff = cLeft - cRight;
} else {
if (isNumericLeft != isNumericRight) {
// One numeric and one char.
if (isNumberRegion)
return isNumericLeft ? 1 : -1;
return cLeft - cRight;
} else {
// Two chars: if (number) diff don't equal 0 return it.
if (diff != 0)
return diff;
// Calculate chars diff.
diff = cLeft - cRight;
if (diff != 0)
return diff;
// Reset!
isNumberRegion = false;
diff = 0;
}
}
}
// The longer one will be put backwards.
return (i == lenLeft && j == lenRight) ? cLeft - cRight : (i == lenLeft ? -1 : 1) ;
}
private boolean isNumeric(char c) {
return c >= '0' && c <= '9';
}
private char getCharByCaseSensitive(char c) {
return caseSensitive ? c : (c >= 'A' && c <= 'Z' ? (char) (c + SPAN_OF_CASES) : c);
}
});
files.forEach(f -> System.out.print(f.getName() + " "));
}
}
输出是，
1.sadasdsadsa 11.asdasdasdasdasd 12_222_222 1_22_2222 2.sadsadasdsad 22.sadasdasdsadsa 2222222222 3.asdasdsadsadsa A__01__02 A__11__23 A__1__23 A__2__02 A__3++++ B__1__02 B__22_13 adsadsadsasd02 adsadsadsasd1 adsadsadsasd10 adsadsadsasd3
1.sadasdsadsa 1_22_2222 2.sadsadasdsad 3.asdasdsadsadsa 11.asdasdasdasdasd 12_222_222 22.sadasdasdsadsa 2222222222 A__01__02 A__1__23 A__2__02 A__3++++ A__11__23 adsadsadsasd02 adsadsadsasd1 adsadsadsasd3 adsadsadsasd10 B__1__02 B__22_13
Process finished with exit code 0
于 2021-07-01T02:43:56.950 回答
-1
// -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;
}
我不太确定是不是你想要的，反正你可以试试:-)
于 2011-01-09T15:00:42.437 回答