我问了this exact question (although in Java)，被指向http://www.davekoelle.com/alphanum.html，那里有一个算法和它在许多语言中的实现。
14年后更新：DaveKoelle的博客已经下线，我找不到他的实际算法，但这里有一个实现。

C++有几种自然排序实现。简要回顾：

• natural_sort<>-基于Boost. Regex。
• 在我的测试中，它大约比其他选项慢20倍。
• Dirk Jagdmann的alnum.hpp，基于Dave Koelle的alphanum algorithm
• 超过MAXINT的值的潜在整数溢出问题
• Martin Pool的natsort-用C编写，但在C++中很容易使用。
• 这是我见过的唯一一个提供大小写不敏感版本的C/C++实现，这似乎是“自然”排序的高优先级。
• 与其他实现一样，它实际上并不解析小数点，但它解析特殊情况下的前导零（任何带有前导0的东西都被假定为分数），这有点奇怪，但可能很有用。
• PHP使用此算法。

这就是所谓的自然排序，有一个算法here看起来很有前途。
注意非ASCII字符的问题（请参见Jeff's blog entry）。

部分重新发布my another answer：

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

为了解决本质上的解析问题，状态机（aka finite state automaton）是一种可行的方法。对上述解决方案不满意，我编写了一个简单的一次性早期纾困算法，该算法在性能方面优于上面建议的C/C++变体，不会遭受数字数据类型溢出错误，并且如果需要，很容易修改以添加大小写不敏感性。
源可以在here中找到

对于那些已经在项目中使用Qt的用户，可以使用QCollator类，详细信息请参见this question。

Avalanchesort是naturall sort的一个递归变体，它在搜索排序数据堆时运行merge。当算法运行/sorting时，即使你向排序堆添加数据，算法也是稳定的。
搜索原则很简单。只有合并才能以相同的秩运行。
找到前两个naturell运行（等级0）后，avalanchesort将其合并为等级1的运行。然后调用avalanchesort生成等级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;

}

}

我的算法与测试代码的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

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

不是很确定是不是你想要的，反正你可以试一试：-）