解题思路

把每个文件夹名从左到右切分成一串“比较单元”：

• 遇到字母：按单个字符作为单元，直接用 ASCII（'A'<'Z'<'a'<'z'）比较
• 遇到连续数字：整段数字作为一个单元，转换成整数值比较（忽略前导 0）

然后用“自然排序”的比较方法从左到右逐单元比较：

1. 单元类型不同：数字单元 < 字母单元
2. 都是字母：按 ASCII 值比较
3. 都是数字：按整数值比较（值相同则继续比较后续单元，不因前导 0 再分胜负）
4. 比到一方结束：若一个是另一个的前缀，短的排前
5. 完全比不出差异：视为相同，保持输入顺序（稳定排序）

相关算法：自定义比较器 + 稳定排序（或在比较相等时用原下标保证稳定）。

复杂度分析

设单个字符串长度为 L（≤127），数量为 n（≤100）。

• 预处理切分：每个字符串 O(L)
• 排序比较：每次比较最坏 O(L)，排序 O(n log n) 次比较 时间复杂度：O(n·L + n log n · L) 空间复杂度：O(n·L)（存储切分结果）

代码实现

Python

import sys
from functools import cmp_to_key

def tokenize(s):
    # 切分为：数字段(0, value) 或 字符(1, ascii)
    tokens = []
    i, n = 0, len(s)
    while i < n:
        c = s[i]
        if '0' <= c <= '9':
            j = i
            while j < n and '0' <= s[j] <= '9':
                j += 1
            # 连续数字转整数（忽略前导0），题目保证长度<=9
            tokens.append((0, int(s[i:j])))
            i = j
        else:
            tokens.append((1, ord(c)))
            i += 1
    return tokens

def cmp_items(a, b):
    ta, tb = a[1], b[1]
    i = 0
    while i < len(ta) and i < len(tb):
        type_a, val_a = ta[i]
        type_b, val_b = tb[i]
        if type_a != type_b:
            return -1 if type_a < type_b else 1  # 数字(0)在前，字母(1)在后
        if val_a != val_b:
            return -1 if val_a < val_b else 1
        i += 1
    # 前缀规则：短的在前
    if len(ta) != len(tb):
        return -1 if len(ta) < len(tb) else 1
    # 完全相同：稳定排序保持输入顺序
    return 0

def solve(names):
    items = [(s, tokenize(s)) for s in names]
    items.sort(key=cmp_to_key(cmp_items))  # Python排序稳定
    return [x[0] for x in items]

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    names = data[1:1+n]
    ans = solve(names)
    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {

    static class Token {
        int type; // 0: 数字段, 1: 字符
        int val;  // 数字值 或 ASCII值
        Token(int type, int val) {
            this.type = type;
            this.val = val;
        }
    }

    static class Item {
        String s;
        ArrayList<Token> tokens;
        int idx; // 原始下标，用于保证稳定
        Item(String s, ArrayList<Token> tokens, int idx) {
            this.s = s;
            this.tokens = tokens;
            this.idx = idx;
        }
    }

    static ArrayList<Token> tokenize(String s) {
        ArrayList<Token> tokens = new ArrayList<>();
        int i = 0, n = s.length();
        while (i < n) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                int j = i;
                while (j < n) {
                    char d = s.charAt(j);
                    if (d < '0' || d > '9') break;
                    j++;
                }
                // 连续数字转整数（忽略前导0），长度<=9，不会溢出int
                int val = Integer.parseInt(s.substring(i, j));
                tokens.add(new Token(0, val));
                i = j;
            } else {
                tokens.add(new Token(1, (int)c)); // ASCII比较
                i++;
            }
        }
        return tokens;
    }

    static int compareTokens(ArrayList<Token> a, ArrayList<Token> b) {
        int i = 0;
        while (i < a.size() && i < b.size()) {
            Token ta = a.get(i), tb = b.get(i);
            if (ta.type != tb.type) {
                return ta.type < tb.type ? -1 : 1; // 数字(0)在前
            }
            if (ta.val != tb.val) {
                return ta.val < tb.val ? -1 : 1;
            }
            i++;
        }
        // 前缀：短的在前
        if (a.size() != b.size()) return a.size() < b.size() ? -1 : 1;
        return 0;
    }

    static List<String> solve(List<String> names) {
        ArrayList<Item> items = new ArrayList<>();
        for (int i = 0; i < names.size(); i++) {
            String s = names.get(i);
            items.add(new Item(s, tokenize(s), i));
        }

        // Java 的 Collections.sort 对对象是稳定的；这里仍用 idx 兜底保证稳定
        Collections.sort(items, new Comparator<Item>() {
            public int compare(Item x, Item y) {
                int c = compareTokens(x.tokens, y.tokens);
                if (c != 0) return c;
                return x.idx - y.idx; // 规则5：保持输入顺序
            }
        });

        ArrayList<String> ans = new ArrayList<>();
        for (Item it : items) ans.add(it.s);
        return ans;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        ArrayList<String> names = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            names.add(br.readLine().trim());
        }
        List<String> ans = solve(names);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ans.size(); i++) {
            sb.append(ans.get(i));
            if (i + 1 < ans.size()) sb.append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

struct Token {
    int type; // 0: 数字段, 1: 字符
    int val;  // 数字值 或 ASCII值
};

struct Item {
    string s;
    vector<Token> tokens;
    int idx; // 原始下标（可选兜底）
};

vector<Token> tokenize(const string& s) {
    vector<Token> tokens;
    int i = 0, n = (int)s.size();
    while (i < n) {
        char c = s[i];
        if (c >= '0' && c <= '9') {
            int j = i;
            while (j < n && s[j] >= '0' && s[j] <= '9') j++;
            // 连续数字转整数（忽略前导0），题目保证<=9位
            int val = 0;
            for (int k = i; k < j; k++) val = val * 10 + (s[k] - '0');
            tokens.push_back({0, val});
            i = j;
        } else {
            tokens.push_back({1, (int)(unsigned char)c}); // ASCII比较
            i++;
        }
    }
    return tokens;
}

int compareTokens(const vector<Token>& a, const vector<Token>& b) {
    int i = 0;
    while (i < (int)a.size() && i < (int)b.size()) {
        if (a[i].type != b[i].type) return a[i].type < b[i].type ? -1 : 1; // 数字在前
        if (a[i].val != b[i].val) return a[i].val < b[i].val ? -1 : 1;
        i++;
    }
    // 前缀：短的在前
    if (a.size() != b.size()) return a.size() < b.size() ? -1 : 1;
    return 0;
}

vector<string> solve(const vector<string>& names) {
    vector<Item> items;
    items.reserve(names.size());
    for (int i = 0; i < (int)names.size(); i++) {
        items.push_back({names[i], tokenize(names[i]), i});
    }

    // 稳定排序：比较相同则保持输入顺序（规则5）
    stable_sort(items.begin(), items.end(), [](const Item& x, const Item& y) {
        int c = compareTokens(x.tokens, y.tokens);
        return c < 0; // 相等时返回false，交给 stable_sort 保持顺序
    });

    vector<string> ans;
    ans.reserve(items.size());
    for (auto &it : items) ans.push_back(it.s);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<string> names(n);
    for (int i = 0; i < n; i++) cin >> names[i];

    vector<string> ans = solve(names);
    for (int i = 0; i < (int)ans.size(); i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

题目内容

文件夹命名经常会使用字符+数字混合命名,为了方便查看，希望文件夹排序时可以按字符序+数字值综合排序。 给定$n$个文件夹名称，每个文件夹名称为$v[i]$，请按照字符从小到大$(a-zA-Z)$及数字值从小到大的顺序排序，输出排序后的文件夹名称。

排序规则:

1.从左到右依次比较，区分大小写，字母从$a-zA-Z$顺序排列

2.连续的数字字符整体转为整数后按从小到大排列，如$001$转为数字$1$后排序

3.字母和数字比较时数字在前，例，'$testcase1$'和'$testcasefail$'排序时'$testcase1$'在前

4.如一个文件夹名称是另一个文件夹名称的前缀子串，则长度短的子串排在前，例:'$testcase,testcase001$'排序时'$testcase$'在前

5.两个文件夹名称排序相同时，不改变输入顺序，这里相同包括数字字符不同但转成整数后值相同，例:'$testcase1$'和'$testcase001$'排序时二者相同，保持输入顺序，'$testcase1$'在前

输入描述

1,第$1$行：$n$，代表输入文件夹名称个数，范围$[1,100]$

2.第2行：$v[0]$代表第$1$个文件夹名称，名称只包合大小写字母和数字字符，长度$[1,127]$，连续的数字字符数量不超过$9$

3.$第n+1$行:$v[n-1]$, 代表第$n$个文件夹名称，名称只包含大小写字母和数字字符,长度$[1,127]$,连续的数字字符数量不超过$9$

输出描述

按行输出排序后的文件夹名称

样例1

输入

3
ts1tc1
ts1tc01
ts0tc1

输出

ts0tc1
ts1tc1
ts1tc01

说明

第$1$行输入$3$,表示有$3$个文件夹

第$3$行起分别输入$3$个文件夹名称'$ts0tc1$'，'$ts1tc1$'，'$ts1tc01$'排序时'$ts$'部分一致，后续'$0$' '$1$' '$1$' 转为数字对应$0,1,1$,按规则排序，'$ts0tc1$'排第$1$，'$ts1tc1$'排经2，'$ts1tc01$'排第$3$

样例2

输入

2
testcase10
testcase9

输出

testcase9
testcase10

说明

第$1$行输入$2$，表示有$2$个文件夹

第$2$行起分别输入$2$个文件夹名称'$testcase10$','$testcase9$'，排序时'$testcase$' 部分一致，然后看最后的数字部分，$9<10$，按数字由小到大排序，'$testcase9$'在前

输出:

$testcase9$

$testcase10$

样例3

输入

3
ts09sc1
ts01tc1
ts010tc12

输出

ts01tc1
ts09tc1
ts010tc12